513
[usaco] Cow Pedigrees
Cow Pedigrees
Silviu Ganceanu -- 2003
Farmer John is considering purchasing a new herd of cows. In this new herd, each mother cow gives birth to two children. The relationships among the cows can easily be represented by one or more binary trees with a total of N (3 <= N < 200) nodes. The trees have these properties:
The degree of each node is 0 or 2. The degree is the count of the node's immediate children.
The height of the tree is equal to K (1 < K <100). The height is the number of nodes on the longest path from the root to any leaf; a leaf is a node with no children.
How many different possible pedigree structures are there? A pedigree is different if its tree structure differs from that of another pedigree. Output the remainder when the total number of different possible pedigrees is divided by 9901.
PROGRAM NAME: nocows
INPUT FORMAT
Line 1: Two space-separated integers, N and K.
SAMPLE INPUT (file nocows.in)
5 3
OUTPUT FORMAT
Line 1: One single integer number representing the number of possible pedigrees MODULO 9901.
SAMPLE OUTPUT (file nocows.out)
2
OUTPUT DETAILS
Two possible pedigrees have 5 nodes and height equal to 3:
@ @
/ \ / \
@ @ and @ @
/ \ / \
@ @ @ @
--------------------------------------------------------------------------------------------------------
這是個典型的動態規劃的問題：
欲求一個高度為K的二叉樹，要從一個等於K-1，一個小於等於K-1的兩個二叉樹構造而來。
關鍵之處在於，用哈希映射來快速的查找。
還有，是自底向上構造二叉樹，還是自上向下的構造二叉樹。根據動態規劃，類似於斐波納旗公式，存在很多重複計算的問題，
因此自底向上計算的，可以減少重複。
還有減枝的問題。對於高度為K的二叉樹，節點數是2×K-1 -》2^k-1;對於超過N的節點，就不必計算了。
這會減少很多計算。
還有，節點數不再這個範圍內的數，直接返回0就不必計算。
我的解法：
--------------------------------------------------------------------------------------------------------
/*
ID: yunleis2
PROG: nocows
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
int ind[203];
class unit
{
public:
int c;
int h;
int n;
unit(int c,int h,int n)
{
this->c=c;
this->h=h;
this->n=n;
}
unit(){}
friend ostream & operator <<(ostream & out,unit u)
{
out<<u.c<<"\t"<<u.h<<"\t"<<u.n<<endl;
return out;
}
};
vector<unit> v;
#define max(x,y) (x>y?x:y)
int main()
{
fstream fin("nocows.in",ios::in);
int N,K;
fin>>N>>K;
unit u(1,1,1);
v.push_back(u);
for(int i=0;i<203;i++)
ind[i]=-1;
int total=0;
int ptr=0;
vector<unit> v1;
bool flag=false;
if((N<(2*K-1))||(N>(pow((double)2,K)-1)))
flag=true;
while(!flag)
{
int i;
for(i=ptr;i<v.size()&&!flag;i++)
{
unit u1=v.at(i);
if((u1.h)>=K)
{
flag=true;
break;
}
for(int j=0;j<=i;j++)
{
unit u2=v.at(j);
int c=1+u1.c+u2.c;
if(c>N)
continue;
int h=max(u1.h,u2.h)+1;
int n=u1.n*u2.n%9901;
if(i!=j)
n=2*n;
unit u(c,h,n);
//v.push_back(u);
//add to the temp vec
if(ind[u.c]==-1){
v1.push_back(u);
ind[u.c]=v1.size()-1;//ind[u.c]=v1.size()-1;
}
else
{
v1.at(ind[u.c]).n+=u.n;
}
}
}
for(int s=0;s<v1.size();s++)
{
v1.at(s).n=v1.at(s).n%9901;
v.push_back(v1.at(s));
ind[v1.at(s).c]=-1;
cout<<v1.at(s);
if(v1.at(s).c==N&&v1.at(s).h==K)
{
flag=true;
total=v1.at(s).n;
break;
}
}
v1.clear();
ptr=i;
}
fstream fout("nocows.out",ios::out);
fout<<total<<endl;
return 0;
}
最後更新：2017-04-02 06:51:49