【题目大意】
整个金字塔为一个有根树结构，根结点为入口，每个结点涂有一种颜色。机器人从入口开始进行DFS，每经过一个结点，它就会记录这个结点的颜色，最后形成一个序列，求对应这个序列可行的树的结构种类数。
【思路解析】
对于序列S，若子串S[l～r]对应一棵子树，则S[l+1]和S[r-1]是进入和离开时产生的。除此之外，[l,r]包含的每棵更深的子树都对应着一个子问题，会产生[l,r]中的一段，相邻两段之间还有途经树根产生的一个字符。因为[l,r]包含的子树个数可能不止两个，如果朴素地枚举子串S[l～r]划分点的数量和所有划分点的位置，那么时间复杂度会很高。
那么我们考虑换一种方法，只考虑子串S[l～r]的第一棵子树是由哪一段构成的。枚举划分点k，令子串S[l+1～k-1]构成[l,r]的第一棵子树，S[k～r]构成[l,r]的剩余部分(其他子树)。如果k不同，那么子串S[l+1～k-1]代表的子树的大小也不同，所以不可能出现重复计算的结果，并且我们可以得到转移方程(f[l][r]表示方案数)：$$if(S[l]\ne S[r])\to f[l][r]=0$$
$$if(S[l]=S[r])\to f[l][r]=f[l+1][r-1]+\sum_{l+2\le k\le r-2,S[l]=S[k]}f[l+1][k-1]*f[k][r]$$初始值：$\forall l\in [1,len(S)],f[l][l]=1$，其余均为0。
目标：f[1][len(S)]
我们发现，对于方案计数类问题，通常一个状态的各个决策之间满足“加法原理”，而每个决策划分的几个子状态之间满足“乘法原理”。在设计状态转移方程的决策方式与划分方法时，一个状态的所有决策之间必须具有互斥性，才能保证不会重复。
【代码实现】
1 #include<bits/stdc++.h> 2 #define rg register 3 #define go(i,a,b) for(rg int i=a;i<=b;i++) 4 #define back(i,a,b) for(rg int i=a;i>=b;i--) 5 #define ll long long 6 #define mem(a,b) memset(a,b,sizeof(a)) 7 using namespace std; 8 const int N=302; 9 const int mod=1e9; 10 int f[N][N]; 11 char S[N]; 12 int work(int l,int r){ 13 if(l>r||S[l]!=S[r]) return 0; 14 if(l==r) return 1; 15 if(f[l][r]!=-1) return f[l][r]; 16 f[l][r]=0; 17 go(k,l+2,r) 18 f[l][r]=(f[l][r]+(ll)work(l+1,k-1)*work(k,r))%mod; 19 return f[l][r]; 20 } 21 int main(){ 22 scanf("%s",S); 23 int n=strlen(S); 24 mem(f,-1); 25 printf("%d\n",work(0,n-1)); 26 return 0; 27 }
原文：https://www.cnblogs.com/THWZF/p/11001656.html
