P10956 金字塔 题解

· · 题解

题目传送门

前置知识

欧拉序 | 区间 DP | 乘法原理

解法

颜色序列本质上是欧拉序，故考虑区间 DP。

设 f_{l,r} 表示 [l,r] 对应的二叉树的个数，状态转移方程为 f_{l,r}=\begin{cases} 1 & l=r \\ [s_{l}=s_{r}] \times \sum\limits_{i=l+2}^{r}[s_{l}=s_{i}] \times f_{l+1,i-1} \times f_{i,r} & l \ne r\end{cases}。

最终，有 f_{1,n} 即为所求。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
const ll p=1000000000;
ll f[400][400];
char s[400];
int main()
{
    ll n,len,l,r,i;
    cin>>(s+1);
    n=strlen(s+1);
    for(i=1;i<=n;i++)
    {
        f[i][i]=1;
    }
    for(len=1;len<=n;len++)
    {
        for(l=1,r=l+len-1;r<=n;l++,r++)
        {
            if(s[l]==s[r])
            {
                for(i=l+2;i<=r;i++)
                {
                    f[l][r]=(f[l][r]+(s[l]==s[i])*f[l+1][i-1]*f[i][r]%p)%p;
                }
            }
        }
    }
    cout<<f[1][n]<<endl;
    return 0;
}

后记

多倍经验：UVA1362 Exploring Pyramids