题意：给定一个序列 问有多少棵树与之对应
题目连接：https://cn.vjudge.net/problem/UVALive-3516
对于这一序列 分两种2情况 当前分支 和 其它分支 用dfs 在当前层的dfs 只讨论当前分支 其他分支 dfs到下一层
构成分支的条件 即为str[i] == str[j] 即首和末相同 然后再去判断着一串上的其它字母 是否符合回溯的条件
#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #define MOD 1000000000 #define LL long long #define ULL unsigned long long #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 10010, INF = 0x7fffffff; char str[maxn]; int d[500][500]; int dfs(int s, int t) {if(s == t) return 1; //如果起点和终点是同一个结点 则可以构成回溯 返回1if(str[s] != str[t]) return 0; //如果起点和终点不相同 则不能回溯if(d[s][t] >= 0) return d[s][t];int ans = 0;for(int i=s+2; i<=t; i++)if(str[i] == str[s]) //如果找到一个和起点相同的点 则就去dfs判断这一条路上的其它结点是符合回溯条件ans = (ans + (LL)dfs(s+1, i-1) * (LL)dfs(i, t)) % MOD; //第二个dfs为其他分支 是从i为起点 t为终点d[s][t] = ans;return ans; } int main() {while(scanf("%s",str) == 1){mem(d, -1);printf("%d\n",dfs(0, strlen(str)-1));}return 0; }