USACO 2.3 Cow Pedigrees

题目描述

Farmer John is considering purchasing a new herd of cows. In this new herd, each mother cow gives birth to two children. The relationships among the cows can easily be represented by one or more binary trees with a total of N (3 <= N < 200) nodes. The trees have these properties:

  • The degree of each node is 0 or 2. The degree is the count of the node's immediate children.
  • The height of the tree is equal to K (1 < K < 100). The height is the number of nodes on the longest path from the root to any leaf; a leaf is a node with no children.

How many different possible pedigree structures are there? A pedigree is different if its tree structure differs from that of another pedigree. Output the remainder when the total number of different possible pedigrees is divided by 9901.

PROGRAM NAME: nocows

Solution

考虑dp,我们设\(dp[i][j]\)为前i个结点小于等于j层的方案数目。每次枚举分给左子结点的点数t,那么n-t-1就是分给右子结点的点数(因为要去掉根结点)。根据乘法原理可以得知,状态转移方程为\(dp[i][j] = \sum_{i=1}^k dp[t][j-1]*dp[i-t-1][j-1]\)

对于初始状态,显然把所有第一维为1的设为1即可。容易想到,枚举点的个数时只用枚举奇数

Code

/*
PROB: nocows
LANG: C++
ID: yizhuor1
*/
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

template <typename T> inline T read(){
    T sum = 0;
    int fl = 1,ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
    for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
    return sum * fl;
}

const int mod = 9901;
const int maxn = 200 + 5;

int n,k;
int dp[maxn][maxn];

inline void Solve (){
    for(int i = 1; i <= k; i++) dp[1][i] = 1;
    for(int l = 1; l <= k; l++){
        for(int i = 3; i <= n; i += 2){
            for(int j = 1; j < i; j += 2){
                dp[i][l] += dp[j][l - 1] * dp[i - j - 1][l - 1];
                dp[i][l] %= mod;
            }
        }
    }
    printf("%d\n",(dp[n][k] - dp[n][k - 1] + mod) % mod);
}

inline void Input (){
    n = read<int>();
    k = read<int>();
}

int main(){
//  freopen("nocows.in","r",stdin);
//  freopen("nocows.out","w",stdout);
    Input();
    Solve();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注