题解 UVA1362 【Exploring Pyramids】

题目大意

给出一棵多叉树，每个结点的任意两个子结点都有左右之分。从根结点开始，每次尽量往左走，走不通了就回溯，把遇到的字母顺次记录下来，可以得到一个序列。如图所示的$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;
}