【寒假每日一题】洛谷 P6489 [COCI2010

寒假每日一题】洛谷 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;
}