自动搬运

查看原文

来自洛谷，原作者为

	251Sec 祈祷着今后的你的人生，永远都有幸福的“魔法”相伴。

搬运于2025-08-24 23:00:26，当前版本为作者最后更新于2024-07-06 18:33:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

官方题解在说啥？？？

只有第一问是简单的，直接 DP 设 $f(i,0/1,0/1)$ 代表前 $i$ 个数，最后一个数是 $a_i$ 还是 $b_i$，最后一个数是否大于倒数第二个数，最大的峰个数。复杂度 $O(n)$。

加上第二问之后，套路地，我们发现最大极差就等价于在序列里任选两个数 $x,y$（可以相同），然后最大化 $x-y$。那么我们在 DP 里再加两维 $0/1$ 代表是否选出了 $x,y$，复杂度 $O(n)$，带巨大常数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, a[500005][2];
struct Node {
	int a, b;
	bool operator<(const Node &o) const {
		if (a != o.a) return a < o.a;
		return b < o.b;
	}
} f[500005][2][2][2][2];
void chkmax(Node &a, Node b) { a = max(a, b); }
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i][0]);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i][1]);
	for (int i = 0; i <= n + 1; i++) {
		for (int p = 0; p < 2; p++) {
			for (int q = 0; q < 2; q++) {
				for (int r = 0; r < 2; r++) {
					for (int s = 0; s < 2; s++) {
						if (p + q + r + s + i) f[i][p][q][r][s] = { (int)-1e9, (int)-1e9 };
					}
				}
			}
		}
	}
	for (int i = 1; i <= n + 1; i++) {
		for (int p = 0; p < 2; p++) {
			for (int q = 0; q < 2; q++) {
				for (int r = 0; r < 2; r++) {
					for (int s = 0; s < 2; s++) {
						for (int np = 0; np < 2; np++) {
							auto t = f[i - 1][p][q][r][s];
							if (q && a[i][np] < a[i - 1][p]) t.a++;
							chkmax(f[i][np][a[i][np] > a[i - 1][p]][r][s], t);
						}
					}
				}
			}
		}
		for (int p = 0; p < 2; p++) {
			for (int q = 0; q < 2; q++) {
				for (int r = 0; r < 2; r++) {
					for (int s = 0; s < 2; s++) {
						if (i <= n) {
							if (r) {
								auto t = f[i][p][q][0][s];
								t.b += a[i][p];
								chkmax(f[i][p][q][r][s], t);
							}
							if (s) {
								auto t = f[i][p][q][r][0];
								t.b -= a[i][p];
								chkmax(f[i][p][q][r][s], t);
							}
						}
					}
				}
			}
		}
	}
	Node res = f[n + 1][0][0][1][1];
	printf("%d\n%d\n", res.a, res.b);
	return 0;
}