USACO 2.3.2 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)

OUTPUT DETAILS

Two possible pedigrees have 5 nodes and height equal to 3:

           @                   @      
          / \                 / \
         @   @      and      @   @
        / \                     / \
       @   @                   @   @

/*------------------------------------------------------------*/

依然是动态规划。一开始我的想法是把树往下延伸找规律，但是这样的话很难找。后来换一种思路，把两棵树合成一棵新的，即根为新增加的结点，左右子树是之前已经计算出来的。那么这个题就好写了，状态转移方程就是

高为h，结点数为n的个数等于高为h-1，结点数为i与所有高小于等于h-1，结点数为n-1-i的个数乘积，再把i从0到n-1求和。

要注意的是，当左右子树完全相同的时候，上面的计算会造成重复。所以一种可行的办法是，左子树高为h-1的时候，右子树高度小于h-1，这样算出来的结果乘以二，再加上左右子树都是h-1的结果。

与之前的一道题一样，这个题有几组数据总是不一样。找了好久也没找出原因，后来才发现，这个题之所以让输出的是模9901的结果是有道理的，当高度和结点数比较大的时候，种类数会十分的大，这个时候不仅int无法存储，连unsigned long也不行了。所以我们在存储的时候，一定要计算一个就让他先模上9901，再存储。否则就会出现数据溢出。不用担心前面模完会不会影响后面的运算，但是我也不知道为什么不用担心。

代码如下：

/*
ID:zhaorui3
PROG:nocows
LANG:C++
*/
# include <fstream>
using namespace std;
unsigned long answer[101][201] = {{0}};

unsigned long pow(int n)
{
	unsigned long out = 1;
	while(n != 0)
	{
		out *= 2;
		n--;
	}
	return out;
}
int main()
{
	ifstream fin("nocows.in");
	ofstream fout("nocows.out");
	int n , k;
	fin >> n >> k;
	answer[0][0] = 1;
	unsigned long tempLeft = 0 , tempRight = 0;
	for(int h = 1 ; h <= k ; h++ )
	{

		for(int m = 1 ; m <= 200 ; m += 2 )
		{
			if(m < 2*h-1)
				continue;
				
			if(m > pow(h) - 1)
				break;

	
			for(int leftN = 0 ; leftN <= m-1 ; leftN++ )
			{
				tempLeft = answer[h-1][leftN];

				tempRight = 0;
				for(int rightH = 0 ; rightH <= h-2 ; rightH++ )
				{
					tempRight += answer[rightH][m-1-leftN];
				}

				answer[h][m] += (2*tempRight * tempLeft ) % 9901;
			}

			for(int N = 0 ; N <= m-1 ; N++ )
				answer[h][m]+= (answer[h-1][N] * answer[h-1][m-1-N]) % 9901;

			answer[h][m] %= 9901;
		}
	}
	fout << answer[k][n] << endl;
	fin.close();
	fout.close();
	return 0;
}

USACO 2.3.2 Cow Pedigrees 仍是动态规划