题意：
科学家用机器人探险地下洞穴，但是机器人只有一个存储器，每到一个洞穴，就会记下洞穴的名字，当有多个洞穴可以进入时，总会选择最左边没有进入过的洞穴，当可选择的洞穴都进过时，他会后退，任意两个洞穴之间只有一条路径，当机器人回来时，科学家根据存储器发现洞穴的结构不是唯一的，他们想知道有多少种可能的结构。
数学模型：
已知一棵树的深度搜索的节点（包括回退）顺序，求树的总数。
分析：
因为答案很大，肯定不可能一一枚举;
设f[i][j]表示从i个点到j个点所能构成的树的总数;
通过枚举回退点来重叠计算，以回退点为根(起点，回退点，终点必须相等),，f[i+1][k-1]*f[k][j];
f[i+1][k-1],表示从第i+1个点到第k-1个点不会回退到根k的树(这是我没有想到的);
f[k][j]的是可以回退到根的，避免了相对结构数的重复计算。
结：
被问题吓到了，感觉自己做不出来就直接看标程了。
主要原因是没有归纳出它的数学模型，被它相对结构和绝对结构给搞混了，不知道怎么从绝对结构转到相对结构。
结论可用来计算树的结构数。
View Code
#include<cstdio> #include<cstring> #define MAXN 310 #define MAX 1000000000 using namespace std; int main() { long long f[MAXN][MAXN]; int i,j,k,n; char s[MAXN]; memset(f,0,sizeof(f)); scanf("%s",s); n=(int)strlen(s); for(i=0;i<n;i++) f[i][i]=1; for(k=2;k<n;k+=2) for(i=0;i+k<n;i++) for(j=i+2;j<=i+k;j+=2) if(s[i]==s[j]&&s[j]==s[i+k]) f[i][i+k]=(f[i][i+k]+f[i+1][j-1]*f[j][i+k])%MAX; printf("%lld",f[0][n-1]); return 0; }