USACO - 2.3.2 - Cow Pedigrees

 

原创文章转载请注明出处

摘要：动态规划

一. 题目翻译

1. 描述：

农民约翰准备购买一群新奶牛。 在这个新的奶牛群中, 每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3 <= N < 200)。这些二叉树有如下性质:

每一个节点的度是0或2。度是这个节点的孩子的数目。

树的高度等于K(1 < K < 100)。高度是从根到最远的那个叶子所需要经过的结点数; 叶子是指没有孩子的节点。

有多少不同的家谱结构? 如果一个家谱的树结构不同于另一个的, 那么这两个家谱就是不同的。输出可能的家谱树的个数除以9901的余数。

2. 格式：

          INPUT FORMAT:

           第1行: 两个空格分开的整数, N和K

          OUTPUT FORMAT:

          第 1 行: 一个整数，表示可能的家谱树的个数除以9901的余数。

3. SAMPLE：

          SAMPLE INPUT:

5 3

          SAMPLE OUTPUT:

2

          

二.  题解

1. 题意理解（将问题分析清楚，大致用什么思路）：

          题目的核心还是动态规划。我们使用count[i][j]表示节点数i、深度为j的数的个数。按照题意，一棵树可以由左子树、右子树构成。那么构造count[i][j]也就是节点数为i、深度为j的一颗树时，有三种情况：1. 左子树深度为i-1，右子树深度小于i-1；2.左子树深度小于i-1，右子树深度为i-1；3.左子树、右子树都是i-1。

          这里要特别注意，深度小于j的树的个数和我们使用count2[i][j]来表示，深度等与j的数的个数我们使用count[i][j]表示。

          最终输出count[num][height]。

 

2. 具体实现（具体实现过程中出现的问题）：

          状态转移方程如下：

          for (int k=1;k<=i-2;k+=2){

count[i][j] = (count[k][j-1]*count2[i-k-1][j-2]+count[i][j])%9901;

count[i][j] = (count2[k][j-2]*count[i-k-1][j-1]+count[i][j])%9901;

count[i][j] = (count[k][j-1]*count[i-k-1][j-1]+count[i][j])%9901;

  }

  count2[i][j] = (count[i][j] + count2[i][j-1])%9901; 

          }    

3. 启示:

        这道题目拓宽了对动态规划使用范围的理解。之前认为动态规划只适用于寻求最优解，而这道题目求解的是一个确定的数字，不是一个最优解。到这道题目我们可以理解为动态规划适用于一个问题可以分解为由若干个子问题组成的情况。

三.  代码

//package session_2_3_2;

/*
ID:fightin1
LANG:JAVA
TASK:nocows
*/
//package session_2_3_2;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.Scanner;

public class nocows {

	/**
	 * @param args
	 * @throws Exception 
	 */
	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(new BufferedReader(new FileReader(
			"nocows.in")));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
			"nocows.out")));
//		Scanner in = new Scanner(System.in);
//		PrintWriter pw = new PrintWriter(System.out);
		
		int num = in.nextInt();
		int height = in.nextInt();
		
		int[][] count = new int[num+1][height+1];
		int[][] count2 = new int[num+1][height+1];
		count[1][1] = 1;
		count2[1][1] = 1;
 		for (int i=1;i<=num;i+=2){
			for (int j=2;j<=height;j++){
				for (int k=1;k<=i-2;k+=2){
					count[i][j] = (count[k][j-1]*count2[i-k-1][j-2]+count[i][j])%9901;
					count[i][j] = (count2[k][j-2]*count[i-k-1][j-1]+count[i][j])%9901;
					count[i][j] = (count[k][j-1]*count[i-k-1][j-1]+count[i][j])%9901;
				}
				count2[i][j] = (count[i][j] + count2[i][j-1])%9901; 
			}
		}
		
		pw.println(count[num][height]);
		pw.close();
	}

}