andyli

题解 UVA1362 【Exploring Pyramids】
题目大意给出一棵多叉树,每个结点的任意两个子结点都有左右之分。从根结点开始,每次尽量往左走,走不通了就回溯,把遇到...
扫描右侧二维码阅读全文
25
2019/01

题解 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;
}
Last modification:June 25th, 2019 at 11:18 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment