洛谷p1216 IOI1994 Day1T1
洛谷p1216 IOI1994 Day1T1
题目描述
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
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
IOI1994 Day1T1
Solution
用一个二维数组存储三角形a[i][j]表示第i行的j个数
1、划分阶段
以每一行为阶段
2、确定状态
用f[i][j]表示状态,表示从第i行第j个开始向下走,所可得的最大值
3、状态转移方程
4、
递推--逆推
先用从下到上的算法
code
//逆推
#include<iostream>
using namespace std;
int max(int a,int b){return a>b?a:b;}
int main(){
int r;
cin>>r;
int triangle[r][r];
for(int i=;i<r;i++)//行
for(int j=;j<i+;j++)//列
cin>>triangle[i][j]; for(int i=r-;i>=;i--)
for(int j=r-;j>=;j--)
triangle[i][j]+=max(triangle[i+][j],triangle[i+][j+]);
cout<<triangle[][];
return ;
}
看!代码是如此的简洁,结构是如此的清晰!
算法讲解
行8~11:输入三角形。
由于三角形一行的个数是行行递增的,
所以
10 for(int j=0;j<i+1;j++)//列
可以使得每行的j的最大值与行号相等。
行13~16:递归计算
从倒数第二行的最后一个数开始,把每一个数([i][j])都加上(+=)它下面的数([i+1][j]),右下角的数([i+1][j+1])中的最大值(max(a,b)).
这里有一个我开始犯的错误:
13 for(int i=r-2;i>=0;i--)
14 for(int j=r-2;j>=0;j--)
15 triangle[i][j]+=max(triangle[i+1][j],triangle[i+1][j+1]);
16 cout<<triangle[0][0];
为什么这里是r-2呢?(之前我就在这里被坑了,本地测试数据答案超大.....)
理解一下:
首先,r是三角形的长宽
又∵第一行第一列是(0,0)
∴最后一行最后一列是(r-1,r-1)
又∵我们是从倒数第二行的最后一个数开始回归的
∴这个数为(r-2,r-2)
最后,行16:输出在首行首列的结果
完毕!
递推--顺推
再用从上到下的算法
f[i][j]=max(f[i-1][j],f[i-1][j-1])
ans=max
深搜dfs
记忆化搜索
在dfs的基础上,再开一二维数组,省去形参,添加返回值
最新文章
- 压缩和解压文件:tar gzip bzip2 compress(转)
- Nginx+PHP优化实例
- NetworkSocket结构图
- 自制Console线(已测试CISCO3560可用)
- 示sudo: cd: command not found
- 二模07day2解题报告
- oracle impdp的table_exists_action详解
- netstat命令查看服务器运行情况
- Android开发之TextView的下划线添加
- [lua]协同式多任务,统筹运用
- C++虚函数在内存中的实现
- iOS进阶
- 各种浏览器开启JavaScript脚本方法
- C语言中全局变量存放在哪个位置?
- Jmeter性能测试之基础知识(一)
- 分块读取Blob字段数据(MSSQL)
- LY.JAVA面向对象编程.工具类中使用静态、说明书的制作过程、API文档的使用过程
- Fragment中生命周期函数的介绍
- (转)C/C++ 程序设计员应聘常见 面试笔试 试题深入剖析
- Linux下CPU信息的查看