Pokémon Army (easyversion) -每天一把CF - 20201007

每天一把CF : 2020-10-07

題目

原題連結:https://codeforc.es/problemset/problem/1420/C1

(今天CF官網抽風,一直在維護,下面的題目描述我是找的別人的部落格里的,是hard版本的,但是也基本知道easy版本是什麼樣子了)
題目已補

思路

題目大意：給你n個數，可以從中選任意個數（至少要選一個）組成一個新的陣列，這個新的陣列的價值計算方式為所有奇數索引項之和減去所有偶數索引項之和，即a1-a2+a3-a4+…問能得到的字數列最大價值是多少。

我們將給定的n個數化成如下的折線圖：

我們首先給出結論->我們要找的那些點就是圖中的峰點和谷點。->證明放在思路的最後

再考慮如何求出這個新的陣列的值：

我們先只考慮如下的abcd四項,其值明顯為a-b+c-d=(a-b)+(c-d)

而a-b的值又等於a到b中每一個小段的長度之和，而每一個小段的長度又等於a[i]-a[i+1]

再注意我們取的a-b和c-d都是下降趨勢的線段,所以只有當a[i]-a[i+1]>0時我們才計算進價值中。

所以總的價值計算方式為：

for (int i = 2; i <= n; i++)
	ans += max(0, a[i] - a[i + 1]);//a是全域性變數,a[n+1]==0

->注意最後一個點的處理方式

再說一句，我們取的點的個數一定是奇數的，因為偶數的話最後一個點是減，反而將價值變小了，不如不取。

若最後一個點是偶數點，則我們不取，將其值加回-- c - d + d

若是奇數點，我們需要加上其值

接下來對我們的結論進行證明:

若在我們選定的點中任意兩個點之間再選取其餘點，則其最終加到價值上的小段數回減少，所以我們原來的取法是最優的。

程式碼實現

#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
const int MAX = 3E5 + 5;


int t, n;
int a[MAX];


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> t;
	while (t--)
	{
		memset(a, 0, sizeof(a));
		cin >> n;
		for (int i = 1; i <= n; i++)
			cin >> a[i];
		int ans = 0;
		for (int i = 2; i <= n; i++)
		{
			ans += max(0, a[i] - a[i + 1]);
		}

		cout << ans << endl;

	}


	return 0;
}