POJ1163-The Triangle-动态规划
2024-08-26 12:34:42
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 50122 | Accepted: 30285 |
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
题意就是三角形走左下角或右上角和max,从下往上找,动态规划。
代码:
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=+;
int main(){
int n,a[N][N];
while(~scanf("%d",&n)){
memset(a,,sizeof(a));
for(int i=;i<n;i++){
for(int j=;j<=i;j++)
scanf("%d",&a[i][j]);
}
for(int i=n-;i>=;i--){
for(int j=;j<=i;j++)
a[i][j]+=max(a[i+][j],a[i+][j+]);
}
printf("%d\n",a[][]);
}
return ;
}
最新文章
- 我的第一个FluentNHibernate例子
- spark发行版笔记10
- apache配置Options详解
- HDU-2604_Queuing
- 自动化运维工具ansible-如何设置客户端多python版本问题
- 通过CSS实现各种方向的三角形
- 数据结构之网络流入门(Network Flow)简单小节
- 201521123012 《Java程序设计》第十三周学习总结
- JAVA基础知识总结:八
- Linux 新建文件/文件夹,删除文件文件夹,查找文件 打开文件
- VMware安装Linux,系统分区。
- 团队项目第二阶段个人进展——Day4
- 001 LRU-缓存淘汰算法
- tomcat操作
- 2.panel面板
- SQLServer分页查询笔记
- koa+orm2
- Lucene原理一
- Android访问网络,使用HttpURLConnection还是HttpClient?
- 在Vue的webpack中结合runder函数
热门文章
- puppet配置问题统计
- Xftp连接阿里云Linux,向Linux上传文件,Windows和Linux文件传输
- 高性能管线式HTTP请求(实践&#183;原理&#183;实现)
- lumen安装后输出hello world
- HTML基本功之文档结构
- Linux发行版 CentOS6.5下删除分区操作
- UNIX域协议(无名套接字)
- IIS加载JSON文件 错误 404
- C#语言和SQL Server第十三 十四章笔记
- vue2.0 路由模式mode=";history";的作用