题目:http://www.nocow.cn/index.php/Translate:USACO/nocows
题意:给定n个节点,求形成高度为k且出度只能为0或2的二叉树的个数。
分析:我们用dp[n][k]来表示n个节点深度为k的上述二叉树的个数。很明显,如果n为偶数,那么dp[n][k]=0,所以我们只
考虑n为奇数的情况。
#include <iostream> #include <string.h> #include <stdio.h> using namespace std; const int MOD = 9901; const int N = 204; const int M = 105; int dp[N][M]; int f[N][M]; void Init() { memset(dp,0,sizeof(dp)); memset(f,0,sizeof(f)); dp[1][1] = 1; for(int k=1;k<M;k++) f[1][k] = 1; for(int k=2;k<M;k++) { for(int i=3;i<N;i+=2) { int sum = 0; for(int j=0;j<=i-2;j++) sum = (sum + dp[j][k-1]%MOD*(f[i-1-j][k-2]%MOD*2 + dp[i-1-j][k-1]%MOD))%MOD; dp[i][k] = sum; f[i][k] = (f[i][k-1]%MOD + dp[i][k]%MOD)%MOD; } } } int main() { int n,k; Init(); while(cin>>n>>k) cout<<dp[n][k]<<endl; return 0; }