寒假每日一题】洛谷 P6489 [COCI2010"/>
【寒假每日一题】洛谷 P6489 [COCI2010
题目链接:P6489 [COCI2010-2011#6] USPON - 洛谷 | 计算机科学教育新生态 (luogu)
题目背景
Tomislav 去爬山。
题目描述
他所走的山路可以看做一个长度为 n 的数字序列 Pi,Pi 表示位置 i 的高度为 Pi。
从低处往高处走一段连续的高度严格递增的山路称为一次爬升。
为了锻炼身体,他想走一段落差尽量大的爬升。
一段山路的落差定义为这段山路的结束点与起始点的差。
你需要求出他走一段山路所能达到最大的落差是多少。
输入格式
输入第一行一个整数 n,表示山路的长度。
第二行 n 个整数 Pi,表示位置 i 的高度为 Pi。
输出格式
输出一行一个整数,表示最大的落差。
如果整条山路不包含任何的爬升,则输出 0。
样例 #1
样例输入 #1
5
1 2 1 4 6
样例输出 #1
5
样例 #2
样例输入 #2
8
12 20 1 3 4 4 11 1
样例输出 #2
8
样例 #3
样例输入 #3
6
10 8 8 6 4 3
样例输出 #3
0
提示
数据规模与约定
对于 100% 的数据,保证 1 <= n <= 1000,1 <= Pi <= 1000。
说明
题目译自 COCI2010-2011 CONTEST #6 T2 USPON。
AC code 1:
#include<iostream>
#include<algorithm>using namespace std;int main()
{int n;cin>>n;int res = 0;for(int i = 0 , x , prenum , t = 0 ; i < n ; i ++){cin>>x;if(i != 0 && x - prenum > 0){t += x - prenum;if(i == n - 1){res = max(res,t);}}else{res = max(res,t);t = 0;}prenum = x;}cout<<res;return 0;
}
AC code 2:(差值矩阵)
#include<iostream>
#include<algorithm>
#include<vector>using namespace std;int main()
{int n;cin>>n;vector<int> a(n);vector<int> dif(n + 1);for(int i = 0 ; i < n ; i ++){cin>>a[i];if(i != 0)dif[i] = a[i] - a[i - 1];}int res = 0;for(int i = 1 , t = 0 ; i <= n ; i ++){if(dif[i] > 0){t += dif[i];if(i == n){res = max(res , t);}}else{res = max(res , t);t = 0;}}cout<<res;return 0;
}
更多推荐
【寒假每日一题】洛谷 P6489 [COCI2010
发布评论