P1472 奶牛家谱 Cow Pedigrees（奇妙的状态定义）

本文主要是介绍P1472 奶牛家谱 Cow Pedigrees（奇妙的状态定义），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

农民约翰准备购买一群新奶牛。在这个新的奶牛群中, 每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有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的二叉树数目。
这是洛谷题解第一篇大牛写的orzhttps://www.luogu.org/problemnew/solution/P1472

这样状态定义，结果就是dp[n][k] - dp[n][k - 1]。转移就直接乘法原理，分配p个到左紫书，j - p - 1到右子树。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int MOD = 9901;
int dp[205][205];//dp[i][j]，i个点小于等于j层int main()
{int n,k;cin >> n >> k;for(int i = 1;i < 205;i++){dp[1][i] = 1;}for(int i = 1;i <= k;i++){for(int j = 3;j <= n;j += 2){for(int q = 1;q < j;q += 2){dp[j][i] = (dp[j][i] + dp[q][i - 1] * dp[j - q - 1][i - 1]) % MOD;}}}cout << (dp[n][k] - dp[n][k - 1] + MOD) % MOD;return 0;
}