博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[POJ] The Triangle
阅读量:5934 次
发布时间:2019-06-19

本文共 1250 字,大约阅读时间需要 4 分钟。

The Triangle
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 47278   Accepted: 28608

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

573 88 1 0 2 7 4 44 5 2 6 5

Sample Output

30

 

//利用动态规划解决问题#include
using namespace std;int a[101][101]; //二维数组储存三角形中的数int main(){ int n; cin>>n; for(int i=0;i
>a[i][j]; for(int i=n-2;i>=0;i--) for(int 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]); //动态规划决策,从后往上加,加到最后最大值为顶端的值 cout<
<

  

转载于:https://www.cnblogs.com/KennyRom/p/6477084.html

你可能感兴趣的文章
vuecli结合eslint静态检查
查看>>
面向对象程序设计-设计模式的一些简单概念
查看>>
JavaScript性能优化大家多多评论谢谢
查看>>
Linq高级查询
查看>>
JQuery 遮罩层弹窗
查看>>
Python学习(20)python操作mysql数据库_安装
查看>>
序列化和反序列化
查看>>
HBase篇--搭建HBase完全分布式集群
查看>>
结对项目 sport club(二)
查看>>
iOS开发UIView.h简介
查看>>
Linux U盘 启动盘
查看>>
文件的上传
查看>>
【robotframework安装】MAC安装
查看>>
传说中的数据结构 栈
查看>>
Codeforces 861 C Did you mean... 模拟 暴力
查看>>
C++基础--STL基本通用函数操作集合
查看>>
延迟加载与单例模式
查看>>
文件写入补充(序列化对象写入)
查看>>
作用域和闭包
查看>>
IP地址分类(A类 B类 C类 D类 E类)
查看>>