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 }
请各位大佬斧正（反正我不认识斧正是什么意思）