Home > Old Blog Posts > USACO 2.3.2 Cow Pedigrees

USACO 2.3.2 Cow Pedigrees


其实这道题原来属于第六章,后来调来第二章了。

这道题也是动态规划,但方程比较难想。

设状态函数为f[i][j],如果把阶段划分为i个结点组成高度恰好为j的二叉树的个数,很难想出状态转移方程。

所以我们改变思路,设f[i][j]为i个节点最多能够建出j层高度的二叉树的个数,那么最后的结果就是f[N][K]-f[N][k-1],这样,状态转移方程就容易得出了:f[i][j]=最多j层高度的左子树的个数*最多j层高度的右子树的个数。

代码:

/*
ID: dementr1
PROG: nocows
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“nocows.in”);
ofstream fout(“nocows.out”);
int f[300][300]={},N,K;
void dp(int i, int j)
{
int k,ans=0;
for(k=1;k<i-1;k+=2)
{
if(f[k][j-1]==-1) dp(k,j-1);
if(f[i-1-k][j-1]==-1) dp(i-1-k,j-1);
ans=(ans+f[k][j-1]*f[i-1-k][j-1])%9901;
}
f[i][j]=ans;
}
int main()
{
int i,j;
fin>>N>>K;
for(i=0;i<=N;i++)
for(j=0;j<=K;j++)
f[i][j]=-1;
for(i=1;i<=K;i++) f[1][i]=1;
dp(N,K);
dp(N,K-1);
int ans=f[N][K]-f[N][K-1];
if(ans<0) ans+=9901;
fout<<ans%9901<<endl;
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: