【寒假每日一题】洛谷 P6489 [COCI2010-2011#6] USPON

题目链接P6489 [COCI2010-2011#6] USPON - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目背景

Tomislav 去爬山。

题目描述

他所走的山路可以看做一个长度为 n 的数字序列 PiPi 表示位置 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 <= 10001 <= 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;
}