题目大意
给出一棵多叉树,每个结点的任意两个子结点都有左右之分。从根结点开始,每次尽量往左走,走不通了就回溯,把遇到的字母顺次记录下来,可以得到一个序列。如图所示的$5$个图的序列均为ABABABA
。给定一个序列,问有多少棵树与之对应。
问题求解
设输入序列为$S$,$d(i,j)$为子序列$S_i$,$S_{i+1}$,…,$S_j$对应的树的个数,则边界条件是$d(i,i)=1$,且$S_i\not= S_j$时$d(i,j)=0$(因为起点和终点应是同一点)。在其他情况下,设第一个分支在$S_k$时回到树根(必须有$S_i=S_k$),则这个分支对应的序列是$S_{i+1}$,…,$S_{k-1}$,方案数为$d(i+1,k-1)$;其他分支对应的访问序列为$S_k$,…,$S_j$,方案数为$d(k,j)$。这样,在非边界情况,递推关系为$d(i,j)=\text{sum}\{d(i+1,k-1)\times d(k,j)|i+2\le k\le j, S_i=S_k=S_j\}$。
参考代码
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 305, MOD = 1000000000;
typedef long long LL;
char S[maxn];
int d[maxn][maxn];
int dp(int i, int j)
{
if (i == j)
return 1;
if (S[i] != S[j])
return 0;
int &ans = d[i][j];
if (ans >= 0)
return ans;
ans = 0;
for (int k = i + 2; k <= j; k++)
if (S[i] == S[k])
ans = (ans + (LL)dp(i + 1, k - 1) * (LL)dp(k, j)) % MOD;
return ans;
}
int main()
{
while (~scanf("%s", S))
{
memset(d, -1, sizeof(d));
printf("%d\n", dp(0, strlen(S) - 1));
}
return 0;
}