UVALive3516Exploring Pyramids（dp）-白红宇的个人博客

UVALive3516Exploring Pyramids（dp）

发布日期：2022-03-13 05:36:13 浏览次数：7 分类：技术文章

本文共 950 字，大约阅读时间需要 3 分钟。

转载请注明出处： ——by fraud

题目意思：有一棵多叉树，每个结点的子节点有左右之分（即要按照顺序查找），从跟结点开始遍历，尽量往左走，走不通就回溯，每到一个结点就记录下结点的信息，最终可以得到一个序列。

　　　　　　所要求的即为给定一个序列，有多少棵树与之对应。

dp[i][j]表示从序列的第i个到第j个所构成的分支的方案数，

边界情况为dp[i][i]=1;如果s[i]!=s[j],则dp[i][j]=0;

递推关系式为dp[i][j]=∑(dp[i+1][k-1]*dp[k][j])；i+2≤k≤j，s[i]=s[j]=s[k]；

1 #include 
      
        2 #include 
       
         3 using namespace std; 4 string s; 5 long long dp[310][310]; 6 const long long MOD=1000000000; 7 long long dfs(int i,int j) 8 { 9     if(i==j)return 1;10     if(s[i]!=s[j])return 0;11     if(dp[i][j]>=0)return dp[i][j];12     dp[i][j]=0;13     for(int k=i+2;k<=j;k++)14     {15         if(s[i]==s[k])16         dp[i][j]=(dp[i][j]+dfs(i+1,k-1)*dfs(k,j))%MOD;17     }18     return dp[i][j];19 }20 int main()21 {22     ios::sync_with_stdio(false);23     while(cin>>s)24     {25         memset(dp,-1,sizeof(dp));26         cout<
        
         <

View Code

转载于:https://www.cnblogs.com/fraud/p/4084251.html

转载地址：https://blog.csdn.net/weixin_30323961/article/details/98235308 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：使用主键或者索引提高SQL语句效率的建议

下一篇：十二丶异常处理

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章