CF484D

首先需要发现一个性质，每个串都是单调的，因为一个不单调的串一定可以拆分成若干个单调的串，并且不劣。

于是用 DP 处理出两个单调串相交的点分给哪个串即可。

具体的话就是设 \(f_i\) 表示前 \(i\) 个位置的答案，如果 \(a_{i-2},a_{i-1},a_i\) 是单调的，那么

否则

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000005;
int n;
int a[N];
ll f[N];

bool chk(int i) {
	if (a[i] > a[i - 1] && a[i - 1] > a[i - 2]) return true;
	if (a[i] < a[i - 1] && a[i - 1] < a[i - 2]) return true;
	return false;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	f[1] = 0, f[2] = abs(a[2] - a[1]);
	for (int i = 3; i <= n; ++i) {
		if (chk(i)) f[i] = f[i - 1] + abs(a[i] - a[i - 1]);
		else f[i] = max(f[i - 1], f[i - 2] + abs(a[i] - a[i - 1]));
	}
	printf("%lld", f[n]);
	return 0;
}

原文地址：http://www.cnblogs.com/Kobe303/p/16897310.html