孤独（Solitude）

251Sec · 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;
}