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

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

相关推荐

    acm poj300题分层训练

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

    常用算法.docx

    1. **搜索算法**:包括最优化剪枝和可行性剪枝,以及树型动态规划。 2. **动态规划**:通过四边形不等式优化状态设计,记录状态的动态规划,以及解决复杂的动态规划问题。 **随机化算法**和**计算几何学**的更高级...

    常用算法 (2).pdf

    - **树型动态规划**:用于解决具有树结构的问题。 - **背包问题**:0-1背包、完全背包、多重背包等。 - **字符串算法**:KMP、Trie、后缀树、后缀数组等。 在学习这些算法时,建议通过实际编程练习来加深理解,可以...

    win7修复本地系统工具

    win7修复本地系统工具

    《自动化专业英语》04-Automatic-Detection-Block(自动检测模块).ppt

    《自动化专业英语》04-Automatic-Detection-Block(自动检测模块).ppt

    《计算机专业英语》chapter12-Intelligent-Transportation.ppt

    《计算机专业英语》chapter12-Intelligent-Transportation.ppt

    西门子S7-1200博图平台下3轴伺服螺丝机程序解析与应用

    内容概要:本文详细介绍了基于西门子S7-1200博图平台的3轴伺服螺丝机程序。该程序使用SCL语言编写,结合KTP700组态和TIA V14及以上版本,实现了对X、Y、Z三个轴的精密控制。文章首先概述了程序的整体架构,强调了其在自动化控制领域的高参考价值。接着深入探讨了关键代码片段,如轴初始化、运动控制以及主程序的设计思路。此外,还展示了如何通过KTP700组态实现人机交互,并分享了一些实用的操作技巧和技术细节,如状态机设计、HMI交互、异常处理等。 适用人群:从事自动化控制系统开发的技术人员,尤其是对西门子PLC编程感兴趣的工程师。 使用场景及目标:适用于希望深入了解西门子S7-1200博图平台及其SCL语言编程特点的学习者;旨在帮助读者掌握3轴伺服系统的具体实现方法,提高实际项目中的编程能力。 其他说明:文中提供的代码示例和设计理念不仅有助于理解和学习,还能直接应用于类似的实际工程项目中。

    MATLAB仿真:非线性滤波器在水下长基线定位(LBL)系统的应用与比较

    内容概要:本文详细探讨了五种非线性滤波器(卡尔曼滤波(KF)、扩展卡尔曼滤波(EKF)、无迹卡尔曼滤波(UKF)、粒子滤波(PF)和变维卡尔曼滤波(VDKF))在水下长基线定位(LBL)系统中的应用。通过对每种滤波器的具体实现进行MATLAB代码展示,分析了它们在不同条件下的优缺点。例如,KF适用于线性系统但在非线性环境中失效;EKF通过雅可比矩阵线性化处理非线性问题,但在剧烈机动时表现不佳;UKF利用sigma点处理非线性,精度较高但计算量大;PF采用蒙特卡罗方法,鲁棒性强但计算耗时;VDKF能够动态调整状态维度,适合信标数量变化的场景。 适合人群:从事水下机器人(AUV)导航研究的技术人员、研究生以及对非线性滤波感兴趣的科研工作者。 使用场景及目标:①理解各种非线性滤波器的工作原理及其在水下定位中的具体应用;②评估不同滤波器在特定条件下的性能,以便为实际项目选择合适的滤波器;③掌握MATLAB实现非线性滤波器的方法和技术。 其他说明:文中提供了详细的MATLAB代码片段,帮助读者更好地理解和实现这些滤波器。此外,还讨论了数值稳定性问题和一些实用技巧,如Cholesky分解失败的处理方法。

    VMware-workstation-full-14.1.3-9474260

    VMware-workstation-full-14.1.3-9474260

    DeepSeek系列-提示词工程和落地场景.pdf

    DeepSeek系列-提示词工程和落地场景.pdf

    javaSE阶段面试题

    javaSE阶段面试题

    《综合布线施工技术》第5章-综合布线工程测试.ppt

    《综合布线施工技术》第5章-综合布线工程测试.ppt

    安川机器人NX100使用说明书.pdf

    安川机器人NX100使用说明书.pdf

    S7-1200 PLC改造M7120平面磨床电气控制系统:IO分配、梯形图设计及组态画面实现

    内容概要:本文详细介绍了将M7120型平面磨床的传统继电器控制系统升级为基于西门子S7-1200 PLC的自动化控制系统的过程。主要内容涵盖IO分配、梯形图设计和组态画面实现。通过合理的IO分配,确保了系统的可靠性和可维护性;梯形图设计实现了主控制逻辑、砂轮升降控制和报警逻辑等功能;组态画面则提供了友好的人机交互界面,便于操作和监控。此次改造显著提高了设备的自动化水平、运行效率和可靠性,降低了维护成本。 适合人群:从事工业自动化领域的工程师和技术人员,尤其是熟悉PLC编程和控制系统设计的专业人士。 使用场景及目标:适用于需要进行老旧设备升级改造的企业,旨在提高生产设备的自动化水平和可靠性,降低故障率和维护成本。具体应用场景包括但不限于金属加工行业中的平面磨床等设备的控制系统改造。 其他说明:文中还分享了一些实际调试中的经验和技巧,如急停逻辑的设计、信号抖动的处理方法等,有助于读者在类似项目中借鉴和应用。

    chromedriver-linux64-136.0.7103.48.zip

    chromedriver-linux64-136.0.7103.48.zip

    IMG_20250421_180507.jpg

    IMG_20250421_180507.jpg

    《网络营销策划实务》项目一-网络营销策划认知.ppt

    《网络营销策划实务》项目一-网络营销策划认知.ppt

    Lianantech_Security-Vulnerabil_1744433229.zip

    Lianantech_Security-Vulnerabil_1744433229

    MybatisCodeHelperNew2019.1-2023.1-3.4.1.zip

    MybatisCodeHelperNew2019.1-2023.1-3.4.1

    《Approaching(Almost)any machine learning problem》中文版第13章(最后一章)

    【深度学习部署】基于Docker的BERT模型训练与API服务部署:实现代码复用与模型共享

Global site tag (gtag.js) - Google Analytics