题解：UVA1362 Exploring Pyramids

思路：

显然的，若不是叶子结点都应该至少遍历两次。

于是两个相同访问之间就可能是一颗子树。

更加具体的，如同 \(s_l,\dots,s_k ,\dots,s_r\)，使得 \(s_l=s_k\)，那么就可以认为 \(s[l,k]\) 是 \(s[l,r]\) 的一颗子树，设区间 \(s[l,r]\) 的结构数量为 \(f_{l,r}\)，那么根据乘法原理，当把 \(s[l,k]\) 看作 \(s[l,r]\) 的第一棵子树时，其方案数为 \(f_{l+1,k-1} \times f_{k,r}\)。

为什么是 \(k+1\) 和 \(l-1\)，是因为那是因为两个子树不能一样，不能重复。

之后区间 DP 即可。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,f[305][305];
const int mod=1e9;
char s[305];
signed main() {
	ios::sync_with_stdio(false);
	while(cin>>s+1){
		memset(f,0,sizeof(f));
		n=strlen(s+1);
		for(int i=1; i<=n; i++)f[i][i]=1;
		for(int i=2; i<=n; i++)
			for(int l=1; l<=n+1-i; l++) {
				int r=l+i-1;
				for(int k=l; k<=r; k++) 
					if(s[l]==s[k]) {
						f[l][r]+=f[l+1][k-1]*f[k][r];
						f[l][r]%=mod;
					}
			}
		cout<<f[1][n]<<"\n";
	}
	return 0;
}

之后更改：

由校友 gaomingyang101011 发现 \(f_{l,k}\) 误写为 \(f_{1,k}\)。