USACO 1.5 Number Triangles
2024-08-30 07:59:38
Number Triangles
Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be 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.
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.
PROGRAM NAME: numtri
INPUT FORMAT
The first line contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.
SAMPLE INPUT (file numtri.in)
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
OUTPUT FORMAT
A single line containing the largest sum using the traversal specified.
SAMPLE OUTPUT (file numtri.out)
30 题目大意:数字三角形,动态规划(DP)入门题目,说的是有一个一群数字排列成三角形,你现在站在上顶点,现在想要走到底边,每次你可以选择走左下或是右下,每次踩到的数字都累加起来,求最大累加和。
思路:这题搜索不好搞,复杂度2^1000简直开玩笑,仔细思索,发现如果我知道脚下的两个点哪个更优,我就有唯一的行走策略了,那就从下往上推,f[i][j]表示从这点出发到达底边的最大累加和,他可以更新它左上的和右上的,从下往上推一遍答案就出来了,就是f[1][1];代码见下面
/*
ID:fffgrdcc1
PROB:numtri
LANG:C++
*/
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int a[][],f[][];
int main()
{
freopen("numtri.in","r",stdin);
freopen("numtri.out","w",stdout);
memset(f,,sizeof(f));
memset(a,,sizeof(a));
int n;
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++)
{
f[i-][j]=max(f[i-][j],f[i][j]+a[i-][j]);
f[i-][j-]=max(f[i-][j-],f[i][j]+a[i-][j-]);
}
}
printf("%d\n",f[][]);
return ;
}
(这题原来写过,所以写的略快,边界的处理比较粗糙,不过因为我提前把边界外一层留了出来且都设为0,所以不会影响答案)
最新文章
- css实现三角效果
- 阿里云日志api创建logStore
- Unity 联网小测试(WWW)
- Struts2拦截器之FileUploadInterceptor
- 你需要知道的Sass插值
- 如何将oc代码转换成运行时代码
- 阿里前CEO卫哲用自己10余年经历,倾诉B2B的三差、四率、两大坑
- ****CSS各种居中方法
- Android 给listview设置分割线与边界的距离
- 关于Http协议的解析
- html5 + css3 + zepto.js实现的微信广告宣传页
- BOM 窗体相关属性以及页面可见区域的获取方式
- twitter 监测登陆活动
- 201521123114 《Java程序设计》第3周学习总结
- PHP session有效期session.gc_maxlifetime详解
- day 14 三元运算符,列表字典推导式,递归,匿名函数,内置函数(排序,映射,过滤,合并)
- Log4j 随笔
- PLSQL oracle32位 oracle64 安装区别及注意问题
- springboot activiti 配置项详解
- 如何批量下载网站中的超链接(一次性下载网页中所有可能的PDF文件)