【2020/11/6每日一题】金字塔
problem
金字塔由若干房间组成，房间之间连有通道。如果把房间看作节点，通道看作边的话，整个金字塔呈现一个有根树结构，节点的子树之间有序，金字塔有唯一的一个入口通向树根。并且，每个房间的墙壁都涂有若干种颜色的一种。探险队员打算进一步了解金字塔的结构，为此，他们使用了一种特殊设计的机器人。这种机器人会从入口进入金字塔，之后对金字塔进行深度优先遍历。机器人每进入一个房间（无论是第一次进入还是返回），都会记录这个房间的颜色。最后，机器人会从入口退出金字塔。显然，机器人会访问每个房间至少一次，并且穿越每条通道恰好两次（两个方向各一次）， 然后，机器人会得到一个颜色序列。但是，探险队员发现这个颜色序列并不能唯一确定金字塔的结构。现在他们想请你帮助他们计算，对于一个给定的颜色序列，有多少种可能的结构会得到这个序列。因为结果可能会非常大，你只需要输出答案对 10^9 取模之后的值。
idea
例如 ABABABA 答案 5
输入是一个回文串，如果不是回文串，肯定方法数是0。
既然要分方法数，那么肯定就和递推或者动态规划有关系。并且数据量肯定满足动态规划。我们思考一下如果这棵树分为几个叉，那么几个叉的方法数肯定就是一个乘积的关系，一个复杂的问题分为多个步骤来完成。
分成几叉的条件是什么，就是在中间出现和根相同的字符，这个条件在题目中尤为重要。所以，这道题的代码就是一个基本的区间 dp 模板。也是区间dp求方法数。
我们以区间长度作为阶段，F[l,r] 表示序列 s[l~r] 中子树的个数。
如果我们从 l 到 r 在每一个点划分一个 k ，那么时间复杂度会很高。一个比较好的想法是，把子串 分成两部分，每部分可由若干子树构成。为了计数重而不漏，我们只考虑子串的第一颗子树是由哪些序列构成的即令子串
构成第一棵子树，
构成剩余部分。
为什么还要加上一个 F[l+1,r-1] 呢？因为我们虽然枚举了第一颗子树，但是却忽略了该树只有一颗子树的情况，所以需要再加上这种情况。
summery
对于方案计数类的动态规划问题，通常一个状态的各个决策之间满足“加法原理”，而每个决策划分的几个子状态之间满足“乘法原理”。在设计状态转移方程的决策方式与划分方法时，一个状态的所有决策之间必须具有互斥性，才能保证不会出现重复问题。
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 309;
const int mod = 1e9;
int f[maxn][maxn];
char a[maxn];
int32_t main() {
cin >> a + 1;
int len = strlen(a + 1);
for (int i = 1; i <= len; i++) f[i][i] = 1;
for (int l = 2; l <= len; l++)
for (int i = 1; i + l - 1 <= len; i++) {
int j = i + l - 1;
if (a[i] != a[j]) continue;
f[i][j] += f[i + 1][j - 1];
for (int k = i + 1; k <= j - 1; k++)
if (a[k] == a[i])
f[i][j] = (f[i][j] + f[i + 1][k - 1] * f[k][j] % mod) % mod;
}
cout << f[1][len];
return 0;
} 
查看29道真题和解析
