洛谷 P1216 [USACO1.5]数字三角形 Number Triangles(水题日常)
2024-09-30 11:16:36
题目描述
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大
输入输出格式
输入格式:
第一个行包含 R(1<= R<=1000) ,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
所有的被供应的整数是非负的且不大于100。
输出格式:
单独的一行,包含那个可能得到的最大的和。
输入输出样例
输入样例#1:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例#1:
30
说明
题目翻译来自NOCOW。
USACO Training Section 1.5
棋盘dp
#include <cstdio>
int R,a[][];
int max(int a,int b){return a>b?a:b;}
int main()
{
scanf("%d",&R);
for(int i=;i<=R;i++)
for(int j=;j<=i;j++)
scanf("%d",&a[i][j]);
for(int i=R-;i>=;i--)
for(int j=i;j>=;j--)
a[i][j]+=max(a[i+][j],a[i+][j+]);
printf("%d",a[][]);
return ;
}
最新文章
- 谨慎使用Sql server data tool 架构比对排除
- IDisposable的另类用法
- linux的零碎使用
- AsyncTask源码分析
- Android之Handler(异步消息处理)机制
- POJ2676-Sudoku(数独)
- require.js优化器
- DllMain加载其他DLL造成的死锁问题及其解决办法
- 单页应用Scrat实践
- C#:求1到100的和
- USACO全部月赛及GateWay数据
- Bootstrap3 排版-改变大小写
- 通过一个例子了解MapReduce
- Mybatis接口编程原理分析(三)
- Linux系统学习之正则表达式
- js判断是否手机自动跳转移动端
- 【Unity笔记】寻路导航用NavMeshObstacle做动态阻挡
- 超全整理!Linux性能分析工具汇总合集
- 图形文件元数据管理工具exiv2
- coursera课程Text Retrieval and Search Engines之Week 4 Overview