好贷网好贷款

UVALive - 3516 Exploring Pyramids

发布时间:2016-12-4 9:55:09 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"UVALive - 3516 Exploring Pyramids",主要涉及到UVALive - 3516 Exploring Pyramids方面的内容,对于UVALive - 3516 Exploring Pyramids感兴趣的同学可以参考一下。

题意:给你一棵多叉树,每个节点的任意两个子节点都有左右之分,从根节点开始尽量往左走,走不通就回溯,把遇到的字母记录下来,可以得到一个序列,给定一个序列,问有 多少棵树与之相应 思路:当sk=si的时候代表回溯到了树根了,那么分支的序列就是si+1,...sk-1,那么就可以设方案数d(i,j)以及它的分支方案数d(i+1,k-1),可以推出关系d(i,j)=sum{d(i+1.k-1)*d(k,j) ,  i+2<=k<=j,si=sk=sj},当si!=sj的时候d(i,j)=0,且d(i,i)=1 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 310; const int mod = 1000000000; typedef long long ll; char s[MAXN]; int d[MAXN][MAXN]; int dp(int i,int j){ if (i == j) return 1; if (s[i] != s[j]) return 0; int &ans = d[i][j]; if (ans > 0) return ans; ans = 0; for (int k = i+2; k <= j; k++) if (s[i] == s[k]) ans = (ans + (ll)dp(i+1,k-1) * (ll)dp(k,j)) % mod; return ans; } int main(){ while (scanf("%s",s) != EOF){ memset(d,-1,sizeof(d)); printf("%d\n",dp(0,strlen(s)-1)); } return 0; }

上一篇:ios7中UIViewControllerBasedStatusBarAppearance作用
下一篇:什么是java序列化,如何实现java序…

相关文章

相关评论