POJ 1163&& 3176 The Triangle(DP)
2024-08-22 21:45:59
The Triangle
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 41169 | Accepted: 24882 |
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.
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
题意:求走过这个三角形时的最大数值。起点为第一行的唯一的那一个数,终点是第n行的某一个数。当中要走dp[i][j]的话。他的上一步仅仅能是dp[i-1][j-1]或者dp[i-1][j];
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h> #define inf 9999
#define INF -9999 using namespace std; int n;
int dp[361][361]; int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
scanf("%d",&dp[i][j]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
dp[i][j] += max(dp[i-1][j-1],dp[i-1][j]);
}
}
int maxx = 0;
for(int i=1;i<=n;i++)
{
if(maxx<dp[n][i])
{
maxx = dp[n][i];
}
}
printf("%d\n",maxx);
}
return 0;
}
最新文章
- .NET环境下基于RBAC的访问控制
- 使用Cobbler无人值守安装CentOS6.5(一)
- ASP.NET MVC 模块与组件(二)——定制图片验证码
- Android驱动入门-LED--测试APP编写③
- Java知多少(下)
- SqlServer根据时段统计数据
- MS SqlSever一千万条以上记录分页数据库优化经验总结【索引优化 + 代码优化】[转]
- oracle 回收站
- Hdu1076(n个闰年后的年份)
- 关于oracle 还原数据库的要领
- Gitlab权限管理-issue管理[六]
- grub2与grub区别
- BZOJ_3872_[Poi2014]Ant colony_dfs
- Pi Hybrids问题
- 守护进程(Daemon)
- python基础_格式化输出(%用法和format用法)
- 解决redis aof文件过大的问题
- jQuery:SP.NET Autocomplete Textbox Using jQuery, JSON and AJAX
- P1031 均分纸牌
- 20155317 2016-2017-2 《Java程序设计》第7周学习总结