[USACO Section 2.3] Cow Pedigrees (动态规划)

题目链接

Solution

我DP太菜啦...
考虑到一棵二叉树是由根节点以及左儿子和右儿子构成。
所以答案其实就是 左儿子方案数*右儿子方案数 。

状态定义:
(f[i][j]) 代表深度为 (i) ,节点个数为 (j) 的二叉树方案数。

转移方程:
对于每一个状态,节点总数已经确定。
那么枚举一维左子树的节点个数,右边用总数减去。

如果要构建一棵深度为 (i) 的二叉树,则两棵子树中必有一棵深度为 (i-1) 。
此时有三种情况:

1. 左子树深度小于 (i-1),右子树深度为 (i-1)。
2. 右子树深度小于 (i-1),左子树深度为 (i-1)。
3. 两边子树深度均为 (i-1)。

由于我们需要的是深度小于 (i-1) 的所有情况,所以记录一个前缀和 (sum) 。
每一次要加上的便是 (sum_{i-2}) 。

然后参照以上做即可。

Code

#include<bits/stdc++.h>
using namespace std;
const int mod=9901;
int f[110][210],n,k,sum[110][210];

int main()
{
    scanf("%d%d", &n, &k);
    f[1][1]=1;
    for (int i=2;i<=k;i++)
        for (int j=1;j<=n;j++)
        {
            for (int p=1;p<j;p++)
            {
                f[i][j]=(f[i][j]+sum[i-2][p]*f[i-1][j-p-1])%mod;
                f[i][j]=(f[i][j]+sum[i-2][j-p-1]*f[i-1][p])%mod;
                f[i][j]=(f[i][j]+f[i-1][p]*f[i-1][j-p-1])%mod;
            }
            sum[i-1][j]=(sum[i-2][j]+f[i-1][j])%mod;
        }
    printf("%d
", f[k][n]);

    return 0;
}