金字塔

传送门

一棵树每个节点用一个字母表示

已知序,求树的可能结构

害,本来想到了区间,冲动了啊

定义表示根为的合法树的数目

此时要求,意思是在原来树的根上再加一个节点

然后枚举一个使得

有转移

意思是仍然以为根,子树之一是

那么现在,区间也是一个相同的子问题了

状态的理解需要非常准确.

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 309;
const int mod = 1e9;
int dp[maxn][maxn];
signed main()
{
    char a[maxn];
    cin >> (a+1);
    int len = strlen(a+1);
    for(int i=1;i<=len;i++)    dp[i][i] = 1;

    for(int l=2;l<=len;l++)
    for(int i=1;i+l-1<=len;i++)
    {
        int j = i+l-1;
        if( a[i]!=a[j] )    continue;    
        dp[i][j]+=dp[i+1][j-1];
        for(int k=i+1;k<=j-1;k++)
            if( a[k]==a[i] )
                dp[i][j] = ( dp[i][j]+dp[i+1][k-1]*dp[k][j]%mod)%mod;
    }
    cout << dp[1][len];
}