USACO 2.3.2 Cow Pedigrees 奶牛家譜
本文正體字版由OpenCC轉換
每個樹的狀態都由其左右子樹狀態決定,根據乘法原理,其狀態數等於左右子樹狀態數乘積 題目限制了數樹的深度
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