首页 > 代码库 > Gym - 101334E 多叉树遍历
Gym - 101334E 多叉树遍历
题意：给定一个字符串，求有多少种树与之对应，对应方式是，每次遍历左节点，没有了，就回溯；
分析:d[i,j] = sum(d[i+1,k-1],d[k,j]) (str[i]==str[k]);
坑点是数组竟然要long long 不然会超时，神奇；
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 }
Gym - 101334E 多叉树遍历
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。