P1472 奶牛家谱 Cow Pedigrees（DP）

题目描述

农民约翰准备购买一群新奶牛。 在这个新的奶牛群中, 每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3 <= N < 200)。这些二叉树有如下性质:

每一个节点的度是0或2。度是这个节点的孩子的数目。

树的高度等于K(1 < K < 100)。高度是从根到最远的那个叶子所需要经过的结点数; 叶子是指没有孩子的节点。

有多少不同的家谱结构? 如果一个家谱的树结构不同于另一个的, 那么这两个家谱就是不同的。输出可能的家谱树的个数除以9901的余数。

输入输出格式

输入格式：

两个空格分开的整数, N和K。

输出格式：

一个整数，表示可能的家谱树的个数除以9901的余数。

输入输出样例

输入样例#1：

5 3

输出样例#1：

2

说明

翻译来自NOCOW

USACO 2.3

dp（i，j）表示i个节点深度为j的树有多少个。那么如果直接转移的话，需要先枚举左子树节点个数k，和一个dep（因为至少有一个子树的深度为j-1）然后如下转移。

dp（i，j）=（dp（k，j-1）* dp（i-k-1，dep））+（dp（k，dep）* dp（i-k-1，j-1））

复杂度明显过高。引入新数组 f（i，j）表示i个节点组成的深度不大于j的个数，那么方程大幅简化，分三种情况，因为至少有一个子树的深度为j-1，所以要么左子树深度为j-1，要么右子树是，要么都是。

dp（i，j）=dp（k，j-1）* f（i-k-1，j-2）+f（k，j-2）* dp（i-k-1，j-1） + dp（k，j-1） * dp（i-k-1，j-1）

然后可以看见只需要枚举k.

AC代码：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
using namespace std;
int i,j,k,l;
const int MOD=9901;
const int maxn=200+10;
const int maxk=100+10;
ll dp[maxn][maxk],f[maxn][maxk];
int main()
{
    int n,K;
    cin>>n>>K;
    dp[1][1]=1;
    f[0][0]=1;
    for(int i=1;i<=K;i++)
       f[1][i]=f[0][i]=1;
    for(int i=3;i<=n;i+=2)
    {
        int j=1;
        while((1<<j)-1<i)j++;
        for(;j<=K;j++)
        {
            for(int k=1;k<=i-1;k+=2)
            {
                dp[i][j]+=dp[k][j-1]*f[i-k-1][j-2];
                dp[i][j]+=f[k][j-2]*dp[i-k-1][j-1];
                dp[i][j]+=dp[k][j-1]*dp[i-k-1][j-1];
            }
            dp[i][j]%=MOD;
        }
        for(int j=1;j<=K;j++) f[i][j]=(f[i][j-1]+dp[i][j])%MOD;
    }
    printf("%lld\n",dp[n][K]);
    return 0;
}