POJ1163(基础线性DP)
2024-09-21 07:01:01
The Triangle
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 42547 | Accepted: 25721 |
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
#include"cstdio"
#include"cstring"
#include"algorithm"
using namespace std;
const int MAXN=;
const int INF=0x3fffffff;
int n;
int a[MAXN][MAXN];
int dp[MAXN][MAXN];
int main()
{
scanf("%d",&n);
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++)
dp[i][j]=max(dp[i+][j],dp[i+][j+])+a[i][j];
printf("%d\n",dp[][]);
return ;
}
最新文章
- 【Codeforces235C】Cyclical Quest 后缀自动机
- 将搜狗词库.scel格式转化为.txt格式
- react native与现有的应用程序集成
- 深入PHP内核之in_array
- Reactor模式与观察者模式
- T—SQL用法剪辑,方便以后查看
- 反序列化 DateTime对象问题
- 【剑指offer】面试题38:数字在排序数组中出现的次数
- 性能优化工具---sar
- Win8.1应用开发之动态磁贴
- CSS规范--春风十里不如写好CSS
- php实现socket推送技术
- IO网络模型
- [HNOI 2017]礼物
- PID control
- loadRunner手动关联,通过 web_reg_save_param()函数
- spring mvc json的输入输出
- AndroidManifest.xml的targetSdkVersion 与 project.properties中target
- 我的QT5学习之路(一)——浅谈QT的安装和配置
- 使用Google Cloud Messaging (GCM),PHP 开发Android Push Notifications (安卓推送通知)
热门文章
- C++11 并发指南五(std::condition_variable 详解)(转)
- Solaris设备管理
- HDMI速率计算
- How to reset your password in Ubuntu
- ubuntu 14.04 LTS 安装webbentch压力測试工具
- Caffe学习系列(12):训练和测试自己的图片--linux平台
- RDLC报表 报表数据 栏 快捷键
- 导入EXCEL 时间数据为小数 问题
- EasyPusher RTSP直播之RTP数据包格式解析
- 九度OJ 1100:最短路径 (最短路径)