Analysis

一棵树的每颗子树都对应着这棵树 DFS 序的一个区间。本题的序列虽然不是 DFS 序列，但也有该性质。本题中，我们以区间长度作为阶段， F[ l , r ] 表示序列 s[ l ~ r ]中子树的个数。

如果我们从 l  到  r  在每一个点划分一个 k ，那么时间复杂度会很高。一个比较好的想法是，把子串s[ l ~ r ]分成两部分，每部分可由若干子树构成。为了计数重而不漏，我们只考虑子串的第一颗子树是由哪些序列构成的，即令子串s[ l+1 ~ k-1 ] 构成第一棵子树，s[ k~r ]构成剩余部分。

为什么这样不会重复呢？因为我们 k 不断向后移动，序列不断加长，也就是说第一颗子树规模在从小变大，当然不会重复；至于剩下部分构成的子树，同理，由于规模不断减小，不可能重复。

为什么还要加上一个F[ l + 1 , r - 1] 呢？因为我们虽然枚举了第一颗子树，但是却忽略了该树只有一颗子树的情况，所以需要再加上这种情况，即F[ l + 1 , r - 1 ]。

对于方案计数类的动态规划问题，通常一个状态的各个决策之间满足“加法原理”，而每个决策划分的几个子状态之间满足“乘法原理”。在设计状态转移方程的决策方式与划分方法时，一个状态的所有决策之间必须具有互斥性，才能保证不会出现重复问题。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stack> 6 #define int long long 7 #define maxn 300+10 8 #define mod 1000000000 9 using namespace std;10 inline int read() 11 {12 int x=0;13 bool f=1;14 char c=getchar();15 for(; !isdigit(c); c=getchar()) if(c==‘-‘) f=0;16 for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-‘0‘;17 if(f) return x;18 return 0-x;19 }20 inline void write(int x)21 {22 if(x<0){putchar(‘-‘);x=-x;}23 if(x>9)write(x/10);24 putchar(x%10+‘0‘);25 }26 int len;27 int dp[maxn][maxn];28 char s[maxn];29 inline int DP(int l,int r)30 {31 if(l>r) return 0;32 if(s[l]!=s[r]) return 0;33 if(l==r) return 1;34 if(dp[l][r]!=-1) return dp[l][r];35 dp[l][r]=0;36 for(int k=l+1;k<=r-1;k++)37  {38 dp[l][r]=dp[l][r]+(DP(l+1,k)*DP(k+1,r))%mod;39 dp[l][r]%=mod;40  }41 return dp[l][r];42 }43 signed main()44 {45 // freopen("pyramid.in","r",stdin);46 // freopen("pyramid.out","w",stdout);47 memset(dp,-1,sizeof(dp));48 scanf("%s",s+1);49 len=strlen(s+1);50 int ans=DP(1,len);51 ans%=mod;52  write(ans);53 return 0;54 }

请各位大佬斧正（反正我不认识斧正是什么意思）