USACO Section 2.3 Cow Pedigrees - DP状态还是很好找的.

这道题一看就是DP...状态的话用dp[n][k]表示n个点k层且符合题目描述的二叉树个数...那么在更新出dp[n][k]值时就枚举下两边的点数和层数情况..每次两边都是种数相乘..最后之和为dp[n][k]的值..这里能取个巧..就是存在大量的左右换一下是同种情况的数..那么可以枚举一边的个数~~再乘2...但这样也要注意在两边同为k-1层时会多计数..所以当两边都为k-1层的情况不能乘2...

Program:

/*  
ID: zzyzzy12  
LANG: C++  
TASK: nocows
*/    
#include<iostream>    
#include<stdio.h>    
#include<string.h>    
#include<math.h>    
#include<algorithm>    
#include<queue> 
using namespace std;  
int n,k;  
int find(int n,int k)
{
     int dp[205][105],sum,i,j,p,t;
     memset(dp,0,sizeof(dp)); 
     dp[1][1]=1; 
     for (i=3;i<=n;i+=2)
        for (j=(int)log2(i)+1;j<i;j++)
        {  
               for (p=j*2-3;p<i;p+=2) 
               { 
                      sum=0;
                      for (t=1;t<j-1;t++) sum+=dp[i-p-1][t];
                      sum%=9901;
                      dp[i][j]=(dp[i][j]+dp[p][j-1]*sum*2)%9901;
                      dp[i][j]=(dp[i][j]+dp[p][j-1]*dp[i-p-1][j-1])%9901;
               } 
        }
     return dp[n][k]; 
} 
int main()
{
     freopen("nocows.in","r",stdin);
     freopen("nocows.out","w",stdout);    
     scanf("%d%d",&n,&k);  
     printf("%d\n",find(n,k));
     return 0;   
}