Description
链接
虽然探索金字塔是极其老套的剧情,但是有一队探险家还是到了某金字塔脚下。经过多年的研究,科学家对这座金字塔的内部结构已经有所了解。首先,金字塔由若干房间组成,房间之间连有通道。如果把房间看作节点,通道看作边的话,整个金字塔呈现一个有根树结构,节点的子树之间有序,金字塔有唯一的一个入口通向树根。并且,每个房间的墙壁都涂有若干种颜色的一种。
探险队员打算进一步了解金字塔的结构,为此,他们使用了一种特殊设计的机器人。这种机器人会从入口进入金字塔,之后对金字塔进行深度优先遍历。机器人每进入一个房间(无论是第一次进入还是返回),都会记录这个房间的颜色。最后,机器人会从入口退出金字塔。
显然,机器人会访问每个房间至少一次,并且穿越每条通道恰好两次(两个方向各一次), 然后,机器人会得到一个颜色序列。但是,探险队员发现这个颜色序列并不能唯一确定金字塔的结构。现在他们想请你帮助他们计算,对于一个给定的颜色序列,有多少种可能的结构会得到这个序列。因为结果可能会非常大,你只需要输出答案对10^9 取模之后的值。
Solution
区间
容易想到设表示的方案数, 当时, 显然
阶段状态已经为, 那么考虑怎么 划分区间, 即 决策
一段区间即表示一颗子树, 而这棵子树可能包含多颗更小的子树, 即可能划分为多个子区间(子问题),
则可以在这段区间中找到合法的分界点, 使得, 将这个区间划分为这两个区间,
也可以理解为: 将 作为第一颗子树, 然后作为另外一部分子树, 由于每次第一颗子树大小不等, 可以保证计数 不重不漏.
而当 时, 可以使得, 表示以为根的只有一个儿子的子树
遵循以上信息, 可以得出 表示区间组成的子树的方案数, 其中为进入和出去产生的字符,
状态转移方程自然也就出来了
使用递归实现即可
Attention
上方的第三个状态转移方程在程序中写成
这是因为时,
时,
Code
#include<bits/stdc++.h>
#define reg register
const int maxn = 305;
const int mod = 1e9;
char S[maxn];
int N;
int dp[maxn][maxn];
int Dp(int l, int r){
if(l > r) return 0;
if(l == r) return 1;
if(S[l] != S[r]) return dp[l][r] = 0;
if(~dp[l][r]) return dp[l][r];
dp[l][r] = 0;
for(reg int k = l+2; k <= r; k ++) dp[l][r] = (1ll*dp[l][r] + 1ll * Dp(l+1, k-1) * Dp(k, r)) % mod;
// if(S[l] == S[r]) dp[l][r] += dp[l+1][r-1]==-1?0:dp[l+1][r-1];
return dp[l][r];
}
int main(){
freopen("pyr.in", "r", stdin);
freopen("pyr.out", "w", stdout);
scanf("%s", S+1);
N = strlen(S+1);
memset(dp, -1, sizeof dp);
Dp(1, N);
printf("%d
", dp[1][N]);
return 0;
}