2.3.2 COW PEDIGREES 奶牛家谱

最新推荐文章于 2019-06-25 23:27:17 发布

T技术沙龙

最新推荐文章于 2019-06-25 23:27:17 发布

阅读量2.3k

点赞数 1

分类专栏： ACM-ICPC 文章标签： acm c++ 算法解题报告

本文链接：https://blog.csdn.net/mmoaay/article/details/40888509

版权

ACM-ICPC 专栏收录该内容

13 篇文章

订阅专栏

解题思路：
1.简单动态规划。基本思想是用小的二叉树去组成大的二叉树，最后输出dp[k][n]-dp[k-1][n]恰好就是要求的n个
    点组成深度最多为k的方法数
2.设dp[i][j]表示j个点组成深度最多为i的二叉树的方法数，则动态规划公式为：
    dp[i][j]=∑(dp[i-1][l]*dp[i-1][j-1-l])(1<=l<=j-2)
    dp[i][1]=1
3.注意：点的个数总为奇数。

核心代码：

for(i=1;i<=k;i++)
        dp[i][1]=1;
    for(i=1;i<=k;i++)
        for(j=3;j<=n;j+=2)
            for(l=1;l<=j-2;l+=2)
                dp[i][j]=(dp[i][j]+dp[i-1][l]*dp[i-1][j-1-l])%9901;