USACO 2.3.2 Cow Pedigrees 奶牛家谱
每个树的状态都由其左右子树状态决定,根据乘法原理,其状态数等于左右子树状态数乘积 题目限制了数树的深度
dp[n,k]=∑(dp[n,k-1]*dp[n-1-i,k-1])(i∈1..i-2) 边界条件：dp[1,i]=1
结果就是 dp[N][K]-dp[N][K-1]
注意考虑与9901求余
/*
ID: cmykrgb1
PROG: nocows
LANG: C++
*/
#include <stdio.h>
FILE *fi,*fo;
long int N,K;
long int dp[201][100];
void dynamicp(void)
{
int i,j,k;
for (j=1;j<=K;j++)
for (i=1;i<=N;i+=2)
for (k=1;k<=i-2;k++)
dp[i][j]=(dp[i][j]+dp[k][j-1]*dp[i-1-k][j-1])%9901;
}
int main(void)
{
int i;
fi=fopen("nocows.in","r");
fo=fopen("nocows.out","w");
fscanf(fi,"%d %d",&N,&K);
fclose(fi);
for (i=1;i<=K;i++)
dp[1][i]=1;
dynamicp();
fprintf(fo,"%ldn",((dp[N][K]+9901-dp[N][K-1])%9901));
fclose(fo);
return 0;
}
上次修改时间 2017-02-03