首页 > 代码库 > UVALive - 3516【多叉树遍历Exploring Pyramids】-----2015年1月27日
UVALive - 3516【多叉树遍历Exploring Pyramids】-----2015年1月27日
一：问题描述
本题题意大致是说：给出一棵多叉树，每个节点的任意两个子节点都有左右之分。从根节点开始，每次尽量往左边走。走不通了就回溯，把遇到的字母顺次记录下来，可以得到一个序列。现在给定一个序列，要求满足条件的多叉树的数目。
二：题目分析
我们可以分析对于这个序列而言一定是对称序列，那么对于序列S而言，
我们定义d(i,j)为子序列
对应的树的个数，边界条件是：
并且我们可以得出如下结论：
在其它情况下，设第一个分支在Sk 时回到树根（必须有Si =Sj ）则这个分支对应的序列是
，方案数为：d(i+1,k-1).其它的分支对应的访问序列是
方案数为d(k,j)。这样在非边界情况下，递推关系为：
三：AC代码
根据这个我们便可以写出代码：
#include<iostream>#include<string.h>#include<math.h>#include<algorithm>using namespace std;#define maxn 300+10#define MOD 1000000000typedef 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+MOD+(ll)dp(i+1,k-1)*(ll)dp(k,j))%MOD; } return ans;}int main(){ while(cin>>s) { memset(d,-1,sizeof(d)); cout<<dp(0,strlen(s)-1)<<endl; } return 0;}
四：总结
本题主要讲解了如何利用递推关系去求解，于此同时我们要学会建立状态。这样才能得出求解方程。
UVALive - 3516【多叉树遍历Exploring Pyramids】-----2015年1月27日
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。