[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;

 }