洛谷 1.5.1 Number Triangles 数字金字塔
2024-08-29 03:50:01
Description
考虑在下面被显示的数字金字塔。 写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。 每一步可以走到左下方的点也可以到达右下方的点。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大和:30
Input
第一个行包含 R(1<= R<=1000) ,表示行的数目。 后面每行为这个数字金字塔特定行包含的整数。 所有的被供应的整数是非负的且不大于100。
Output
单独的一行包含那个可能得到的最大的和。
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
经典入门DP题。
如果从最后一层到第一层的话,第一层的数必然由第二层的最大的一个数(以下几层的和)相加而来,第二层同理,第三层如是。
有一个策略是肯定正确的,就是两个数相比,必然是取大的那个。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0);
const double e=exp();
const int N = ; int dp[][];
int main()
{
int i,p,j;
int n,t;
scanf("%d",&n);
for(i=;i<n;i++)
{
for(j=;j<=i;j++)
{
scanf("%d",&dp[i][j]);
}
}
for(i=n-;i>=;i--)
{
for(j=;j<=i;j++)
{
dp[i][j]+=max(dp[i+][j],dp[i+][j+]);
}
}
printf("%d\n",dp[][]);
return ;
}
最新文章
- pat甲级题解(更新到1013)
- iis 7.5应用程序池自动停止
- JavaScript基础1
- LruCache--远程图片获取与本地缓存
- osvdb
- Swift—默认构造函数-备
- Codeforces Round #199 (Div. 2) B. Xenia and Spies
- linux--shell script
- Effective C++(14) 在资源管理类中小心copying行为
- 『2019/3/8 USACO测试 反思与总结』
- Scanner和BufferReader的效率问题
- GMA Round 1 三角形
- 通过DMS连接RDS需要添加的DMS白名单地址
- Java集合之HashSet源码分析
- Schiff Move Free维骨力这个牌子的保健效果怎么样,是要给中老年人群服用的
- MAC 设置环境变量path的常用方法
- 使用HTML引用标签来分隔Ticket回复
- bzoj 4919 [Lydsy1706月赛]大根堆 set启发式合并+LIS
- IO模型(阻塞、非阻塞、多路复用与异步)
- 判断 checkbox 是否选中以及 设置checkbox选中
热门文章
- 简述Java中Http/Https请求监听方法
- mysql的程序组成
- PHP 操作redis 详细讲解 转的 http://www.cnblogs.com/jackluo/p/3412670.html
- 虚拟机中安装 centOS,本地安装 SSH 连接 - 02
- jquery截取手机号中间4位数,然后变为*
- UVA11737_Extreme Primitive Society
- EM算法[转]
- 【bzoj2669】[cqoi2012]局部极小值 容斥原理+状压dp
- BZOJ4999 This Problem Is Too Simple!(树上差分+dfs序+树状数组)
- pycharm中新建并且运行django