`
richard_ma
  • 浏览: 16173 次
最近访客 更多访客>>
社区版块
存档分类
最新评论

poj1163 树型结构动态规划和最大路径

阅读更多
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个,比较这两个路径的和,选择大的加上本节点的值,作为本节点的值(前驱节点的和)。

最终第一个元素的值就是最大路径求得的和。

#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;
}
分享到:
评论

相关推荐

    POJ1163-The Triangle

    在"The Triangle"题目中,可能需要遍历一个二维数组,从顶部到底部寻找一条经过的路径,使得路径上的元素之和最大。 2. **二维数组处理**:题目可能会给出一个表示三角形的二维数组,每行的元素代表三角形的一层,...

    北大POJ1163-The Triangle

    北大POJ1163-The Triangle

    北大POJ初级-动态规划

    动态规划适用于那些具有重叠子问题和最优子结构的优化问题,如背包问题、最长公共子序列、斐波那契数列等。 在北大POJ初级阶段,动态规划的题目可能涵盖基础的最短路径问题、最长递增子序列、矩阵链乘法、剪枝操作...

    poj dp总结,动态规划分类

    根据题目编号和题目名称,我们可以对POJ上的动态规划题目进行初步分类: 1. **基础动态规划** - **1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609...

    poj经典动态规划题目解题报告

    poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...

    POJ 1015 动态规划

    POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。

    动态规划算法poj1088滑雪实验报告

    动态规划是一种解决最优化问题的有效方法,尤其适用于具有重叠子问题和最优子结构的问题。在滑雪问题中,给定一个二维数组表示地形高度,任务是找出从任意一点开始能够滑行的最长下坡路径的长度。这里的“最长下坡...

    经典动态规划合集_牛人 树形,压缩 老题

    3.徐持衡《浅谈几类背包题》 8.徐源盛《对一类动态规划问题的研究》 背包九讲Pack ...树型动态规划和状态压缩动态规划 算法导论第15章-动态规划 最长公共子序列和字符串相似度 最大矩阵连乘次数(最小连乘变形)

    POJ动态规划题目全面总结

    PKU Online Judge上面很全面的动态规划试题总结。动态规划是ACM考点中最重要的一大类算法之一,对于工作人员来说,动态规划也是实际开发中经常会遇到的算法。这是POJ上面很多DP题目的总结与深刻分析。利于算法学习,...

    POJ1015-Jury Compromise【动态规划DP】

    POJ 1015是题目在POJ平台上的唯一标识,"Jury Compromise"是题目的英文名称,而"动态规划"和"DP"则是指用于解决问题的算法。 【压缩包子文件的文件名称列表】中的 "POJ1015-Jury Compromise.cpp" 是C++语言编写的源...

    acm poj300题分层训练

    6. **更复杂的动态规划**:poj1191、poj1054等题目增加了动态规划的难度,引入了记录状态的DP和树型DP。 7. **数学**:poj1286、poj2409等继续深入组合数学,poj1226、poj1961等训练了KMP算法,poj3440、poj3071等...

    POJ算法题目分类

    图算法是指解决图相关问题的算法,包括图的深度优先遍历和广度优先遍历、最短路径算法、最小生成树算法、拓扑排序、二分图的最大匹配等。 * 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指...

    poj经典数据结构题目解题报告

    在ACM竞赛中,Poj平台上的数据结构题目常常考验选手对算法的深入理解和高效实现。本篇解题报告主要探讨了Pku ACM 3253 Fence Repair问题,这是一道涉及哈夫曼编码(Huffman Coding)的题目。哈夫曼编码是一种用于...

    POJ 分类题目 txt文件

    例如,题目poj3267和poj1836就属于动态规划问题,其中poj1836需要通过动态规划找到最优的编辑距离。 ### 5. 数学算法 数学算法涵盖代数、几何、数论等多个领域,常见的有组合数学、概率统计、矩阵运算等。数论中...

    ACMer需要掌握的算法讲解 (2).docx

    * 树型动态规划:POJ2057、POJ1947、POJ2486、POJ3140 五、计算几何学 * 坐标离散化:POJ3429 * 代码快速写成,精简但不失风格:POJ2525、POJ1684、POJ1421、POJ1048、POJ2050、POJ3306 * 保证正确性和高效性:POJ...

    北京大学-动态规划-讲解PDF

    文档还通过一个具体的实例——POJ1163数字三角形问题来演示动态规划的工作方式。在这个问题中,需要在数字构成的三角形中找到一条从顶点到底边的路径,并使路径上数字之和最大。由于路径的每个步骤只能向左下或右下...

    poj题目分类

    * 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...

Global site tag (gtag.js) - Google Analytics