usaco：Cow Pedigrees

本文主要是介绍usaco：Cow Pedigrees，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

dp原理：

（1）dp[i][j] 表示 i 个节点建 <= j 层树的结果数。结果：res[n][k] = dp[n][k] - dp[n][k-1]（res[i][j] 表示用 i 个节点建 j 层数的结果数）；

（2）dp[i][j] = E(dp[k][j - 1] * dp[i - k - 1][j - 1])(1 <= k <= i - 2)（E为求和）；

（3）注意（2）中k每次加2，因为左右子树的节点数都是奇数。

/*
ID: 
LANG: C++
TASK: nocows
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>#define IN "nocows.in"
#define OUT "nocows.out"
#define M 205
#define MOD 9901using namespace std;int dp[M][M];
int n, k;
void solve()
{for(int i = 1; i <= k; i++)dp[1][i] = 1;for(int i = 2; i <= k; i++) {for(int j = 1; j <= n; j++) {for(int l = 1; l <= j - 2; l += 2) {dp[j][i] += (dp[l][i - 1] * dp[j - l - 1][i - 1]) % MOD;dp[j][i] %= MOD;}}}
}int main()
{freopen(IN, "rb", stdin);freopen(OUT, "wb", stdout);while(scanf("%d%d", &n, &k) != EOF) {solve();printf("%d\n", (MOD + dp[n][k] - dp[n][k - 1]) % MOD);}fclose(stdin);fclose(stdout);return 0;
}

这篇关于usaco：Cow Pedigrees的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---