The Triangle
http://poj.org/problem?id=1163
http://acm.hdu.edu.cn/showproblem.php?pid=2084
Description
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(Figure 1)
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
Input
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
Output
Your program is to write to standard output. The highest sum is written as an integer.
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
Source
IOI 1994
这是一个树型结构的路径选择问题,要求选择出的路径和最大。很明显这里不能使用贪心策略,因为某一步的最大值可能影响后面的路径选择,而在后续的路径中求和“吃亏”。所以应该使用动态规划。
自底向上,每个数字对应的可能路径为2个,比较这两个路径的和,选择大的加上本节点的值,作为本节点的值(前驱节点的和)。
最终第一个元素的值就是最大路径求得的和。
http://poj.org/problem?id=1163
http://acm.hdu.edu.cn/showproblem.php?pid=2084
Description
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(Figure 1)
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
Input
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
Output
Your program is to write to standard output. The highest sum is written as an integer.
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
Source
IOI 1994
这是一个树型结构的路径选择问题,要求选择出的路径和最大。很明显这里不能使用贪心策略,因为某一步的最大值可能影响后面的路径选择,而在后续的路径中求和“吃亏”。所以应该使用动态规划。
自底向上,每个数字对应的可能路径为2个,比较这两个路径的和,选择大的加上本节点的值,作为本节点的值(前驱节点的和)。
最终第一个元素的值就是最大路径求得的和。
#include <stdio.h> #include <stdlib.h> int main (int argc, char const* argv[]) { int i, j, n, a[100][100]; scanf("%d", &n); for (i = 0; i < n; i++) { for (j = 0; j <= i; j++) { scanf("%d", &a[i][j]); } } for (i = n-2; i >= 0; i--) { for (j = 0; j <= i; j++) { a[i][j] += a[i+1][j] > a[i+1][j+1] ? a[i+1][j] : a[i+1][j+1]; } } printf("%d\n", a[0][0]); return 0; }
发表评论
-
fhloj1051 投票
2013-07-04 19:42 0投票 源文件: b(.bas/.c/.cpp/.pas) 输 ... -
fhloj1050 足球赛
2013-07-04 19:36 558足球赛 源文件: a(.bas/.c/.cpp/.pas) ... -
fhloj1092 五子棋
2013-07-04 12:01 665五子棋 源文件: gobang(.bas/.c/.cpp/ ... -
fhloj1091 拼单词
2013-07-04 11:53 702拼单词 源文件: words ... -
fhloj1090 21点游戏
2013-07-04 11:44 59121点游戏 源文件: poker(.bas/.c/.cpp ... -
fhloj1089 帮奶奶算帐
2013-07-04 11:17 557帮奶奶算账 源代码:bill.bas/pas 输入文件:bil ... -
hdu1019 gcd和lcm
2012-12-06 15:09 735Least Common Multiple http://a ... -
hdu1021 推理规律
2012-12-06 09:24 887Fibonacci Again http://acm.hdu ... -
hud1008 电梯 迭代模拟计算
2012-12-04 18:24 986Elevator http://acm.hdu.edu.cn ... -
hdu1001 求和
2012-12-03 22:05 719Sum Problem http://acm.hdu.edu ... -
hdu1000 A+B
2012-12-03 18:37 777A + B Problem http://acm.hdu.e ... -
hdu2035 乘方取余
2012-12-02 18:02 1035人见人爱A^B http://acm.hdu.edu.cn/ ... -
hdu2034 差集
2012-12-02 17:43 809人见人爱A-B http://acm.hdu.edu.cn/ ... -
hdu2033 时间计算
2012-12-02 16:24 853人见人爱A+B http://acm.hdu.edu.cn/ ... -
HDU1003最大连续子序列和
2012-12-01 15:08 1399Max Sum http://acm.hdu.edu.cn/ ... -
hdu2081 字符串拼接
2012-12-01 14:35 772手机短号 http://acm.hdu.edu.cn/sho ... -
POJ1579递归函数定义
2012-11-30 21:58 805Function Run Fun http://poj.or ... -
POJ1050 最大子矩阵
2012-11-30 11:34 1150To the Maxhttp://poj.org/proble ...
相关推荐
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1163-The Triangle
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
北大POJ初级-动态规划 解题报告+AC代码
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
PKU Online Judge上面很全面的动态规划试题总结。动态规划是ACM考点中最重要的一大类算法之一,对于工作人员来说,动态规划也是实际开发中经常会遇到的算法。这是POJ上面很多DP题目的总结与深刻分析。利于算法学习,...
3.徐持衡《浅谈几类背包题》 8.徐源盛《对一类动态规划问题的研究》 背包九讲Pack ...树型动态规划和状态压缩动态规划 算法导论第15章-动态规划 最长公共子序列和字符串相似度 最大矩阵连乘次数(最小连乘变形)
poj经典数据结构题目解题报告poj经典数据结构题目解题报告
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
动态规划算法poj1088滑雪实验报告 动态规划算法poj1088滑雪实验报告
POJ上的DP分类: 容易: 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵,求...
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj online judge 1050 最大子矩阵动态规划解决
动态规划DP题解 POJ HDU 动态规划解题报告
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
动态规划DP题解 POJ HDU部分动态规划DP题解