题解：P15615 [ICPC 2021 Jakarta R] Maxdifficent Group

· · 题解

题目传送门

这题最大的难度在于看懂题目。把这一大段看起来离人很远的描述翻译成人话就是：把原序列划分为若干子段，每个子段贡献为其中元素之和，求相邻子段贡献之差的绝对值最大能是多少。

我们贪心的考虑，要使相邻子段贡献之差最大化，必然要使一边的贡献取到最大值，一边取到最小值。我们枚举贡献差最大的两相邻子段的分界点 i，记 s_0=\max_{j=1}^{i}{(\sum_{k=j}^{i}A_k)}，s_1=\min_{j=1}^{i}{(\sum_{k=j}^{i}A_k)},s_2=\max_{j=i+1}^{n}{(\sum_{k=i+1}^{j}A_k)},s_3=\min_{j=i+1}^{n}{(\sum_{k=i+1}^{j}A_k)}，该点作为分界点的答案必然为 s_0-s_3 或是 s_2-s_1，取较大值即可。证明如下：

假设以点 i 为分界的答案不是上述两种，则记此时两侧的子段和分别为 s_4, s_5，当 s_4<s_5 时，该点答案为 s_5-s_4，根据定义，必然有 s_2-s_5\ge0,s_4-s_1\ge0，将 s_5,s_4 换成 s_2,s_1 必然不劣。若 s_4>s_5，同理可得 s_0-s_3 必然不劣，假设不成立，原命题得证。

然而暴力求解 s_0,s_1,s_2,s_3 是 O(n^2) 的时间复杂度。但是这四个量可通过递推求出，以 s_0 为例，可以通过取 i-1 的 s_0'+A_i 与 A_i 取较大值获得，其余三个同理。

AC Code

总时间复杂度为 O(n)。

#include<bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 1e5+5;
int n;
LL a[N], psum[2][N], bsum[2][N], ans = -1e18;

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        psum[0][i] = max(psum[0][i-1]+a[i], a[i]);//s0
        psum[1][i] = min(psum[1][i-1]+a[i], a[i]);//s1
    }
    for(int i = n; i >= 1; i--) {
        bsum[0][i] = max(bsum[0][i+1]+a[i], a[i]);//s2
        bsum[1][i] = min(bsum[1][i+1]+a[i], a[i]);//s3
    }
    for(int i = 1; i < n; i++) {
        ans = max(ans, max(psum[0][i]-bsum[1][i+1], bsum[0][i+1]-psum[1][i]));
    }
    printf("%lld\n", ans);

    return 0;
}