- 浏览: 37658 次
- 性别:
- 来自: 北京
最新评论
-
andyshar:
请问如何在现有的hadoop环境中安装?
Hadoop集群监控系统Ambari安装 -
qingtangpaomian:
失败123 写道您好楼主: 我装好之后为啥老是最后一 ...
Hadoop集群监控系统Ambari安装 -
失败123:
您好楼主: 我装好之后为啥老是最后一步Cluster ...
Hadoop集群监控系统Ambari安装
原创文章转载请注明出处
摘要:动态规划
一. 题目翻译
1. 描述:
农民约翰准备购买一群新奶牛。 在这个新的奶牛群中, 每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3 <= N < 200)。这些二叉树有如下性质:
每一个节点的度是0或2。度是这个节点的孩子的数目。
树的高度等于K(1 < K < 100)。高度是从根到最远的那个叶子所需要经过的结点数; 叶子是指没有孩子的节点。
有多少不同的家谱结构? 如果一个家谱的树结构不同于另一个的, 那么这两个家谱就是不同的。输出可能的家谱树的个数除以9901的余数。
2. 格式:
INPUT FORMAT:
第1行: 两个空格分开的整数, N和K
OUTPUT FORMAT:
第 1 行: 一个整数,表示可能的家谱树的个数除以9901的余数。
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();
}
}
发表评论
-
USACO - 3.2.2 - Stringsobits
2012-08-23 16:02 805原创文章转载请注明 ... -
USACO - 3.2.1 - Factorials
2012-08-23 16:01 697原创文章转载请注明出处 摘要:动态规划 ... -
USACO - 3.1.6 - Stamps
2012-08-23 16:01 1035原创文章转载请注明 ... -
USACO - 3.1.5 - Contact
2012-08-23 16:01 907原创文章转载请注明出处 摘要:二叉树的应用 , ... -
USACO - 3.1.3 - Humble Numbers
2012-08-23 16:00 711原创文章转载请注明 ... -
USACO - 3.1.2 - Score Inflation
2012-08-22 10:05 903原创文章转载请注明出处 摘要:动态规划 ... -
USACO - 3.1.1 - Agri-Net
2012-08-22 10:04 853原创文章转载请注明出处 摘要:Prim算法 , ... -
USACO - 2.4.5 - Fractions to Decimals
2012-08-22 10:04 959原创文章转载请注明出处 摘要:模拟 , 数论 ... -
USACO - 2.4.4 - Bessie Come Home
2012-08-22 10:04 903原创文章转载请注明出处 摘要:Dijkstra ... -
USACO - 2.4.2 - Overfencing
2012-08-22 10:03 998原创文章转载请注明 ... -
USACO - 2.4.1 - The Tamworth Two
2012-08-21 10:37 716原创文章转载请注明出处 摘要:模拟 ... -
USACO - 2.3.5 - Controlling Companies
2012-08-21 10:37 1300原创文章转载请注明出处 摘要:BFS , 模拟 ... -
USACO - 2.3.4 - Money Systems
2012-08-21 10:37 866原创文章转载请注明 ... -
USACO - 2.3.3 - Zero Sum
2012-08-21 10:36 742原创文章转载请注明出处 摘要:dfs , 枚举 ... -
USACO - 2.3.1 - Longest Prefix
2012-08-20 20:31 1040原创文章转载请注明 ... -
USACO - 2.2.4 - Party Lamps
2012-08-20 20:30 1207原创文章转载请注明出处 摘要:枚举,三星 ... -
USACO - 2.2.3 - Runaround Numbers
2012-08-20 20:30 658原创文章转载请注明 ... -
USACO - 2.2.2 - Subset Sums
2012-08-20 20:30 694原创文章转载请注明出处 摘要:动态规划 ,0- ... -
USACO - 2.2.1 - Preface Numbering
2012-08-20 20:29 890原创文章转载请注明出处 摘要:模拟 , 数学分析 ... -
USACO - 2.1.5 - Hamming Codes
2012-08-18 19:22 781原创文章转载请注明出处 摘要:枚举、暴力 ...
相关推荐
USACO题目,Greedy Gift Givers
此c++代码实现了USACO上Bessie Come Home的问题,并运用了弗洛伊德算法
此C++程序是实现了USACO网站上的Magic Squares的问题。
该题来自USACO,为最长串的查找,此处方法很笨,有更好方法
USACO chapter one.May hope it useful to someone
USACO chapter two.Useful for beginners.
usaco 上的题目barn1,beads,calfflac,可到那里查看具体题目
Notes-USACO-2021-弹簧
USACO-Cpp
C-Usaco-Work:Usaco在C中的工作
USACO-实践USACO 培训网站的工作实践代码! 100% 工作 - 大部分优化 - 混合语言
这是USACO2001-2007月赛全集。 usaco是美国中学生的官方竞赛网站。是美国著名在线题库,专门为信息学竞赛选手准备。推荐直接阅读英语原文,既准确可靠又可提高英语水平。做题方式模拟正式比赛,采用标准测评机、文件...
资源包包括USACO 2001-2007年月赛的测试数据;usaco月赛十年题典(2000-2009),usaco月赛2002-2008题解。单独下载需资源分30分以上。为了方便编程爱好者,我这边统一下载打包。欢迎下载。
USACO培训网站 我为章节解决方案。 每个文件的多行USACO标识信息注释 第1章全部的解决方案 第2章全部的解决方案
USACO-TurtleCamera 该存储库包含我对USACO问题的所有解决方案。 CSE 199工作区目录将是我用来帮助开发USACO课程的主要目录。
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
我的USACO题解和程序
Java中的USACO金问题 YYMM 姓名 文件夹 笔记 代码 1812 美食 1812 牛适应性 1812 团队合作
USACO-Guide
USACO培训页面美国计算机奥林匹克训练页2015年6月17日开始