Gym - 101334E 多叉树遍历

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int maxn = 300+5;
 6 const int mod = 1000000000;
 7 char str[maxn];
 8 int d[maxn][maxn];
 9 
10 
11 int dp(int i,int j) {
12     if(i==j) return 1;
13     if(str[i]!=str[j]) return 0;
14     int& ans = d[i][j];
15     if(ans>=0) return ans;
16     ans = 0;
17 
18     for(int k=i+2;k<=j;k++) {
19         if(str[i]==str[k]) {
20             ans = (ans + (long long)dp(i+1,k-1)*(long long)dp(k,j)) % mod;
21         }
22     }
23     return ans;
24 }
25 
26 int main()
27 {
28     freopen("exploring.in","r",stdin);
29     freopen("exploring.out","w",stdout);
30     while(scanf("%s",str)!=EOF) {
31         memset(d,-1,sizeof(d));
32         printf("%d\n",dp(0,strlen(str)-1));
33     }
34     return 0;
35 }