题解：P2545 [AHOI2004] 实验基地

xuan_never · 2024-05-11 10:33:29 · 题解

题目传送门

简化题意

给出 2 个 N 的数列 a,b，找到一对 l,r 使 a,b 中 l\sim r 的和减 a 中 l+1\sim r-1 的最小非空子段和最大。

做法

区间和可以用前缀和 O(n) 维护，而最小非空子段和可以用 O(n^2) 预处理（记录包含左端点的最小子段和包含右端点的最小子段和）。
最后枚举上述的 l,r 寻找最大的值就可以了，总体时间复杂度 O(n^2)。

代码

#include <bits/stdc++.h>
using namespace std;
long long n, a[2003], b[2003], f[2003][2003], lf[2003][2003], rf[2003][2003], ans = LONG_LONG_MIN;
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
            cin >> a[i],
            f[i][i] = lf[i][i] = rf[i][i] = a[i],
            a[i] += a[i - 1];
    for (int l = 2; l <= n; ++l)
        for (int i = 1, j = l, m = j + 1 >> 1; j <= n; ++i, ++j, ++m)
            lf[i][j] = min(lf[i][m], a[m] - a[i - 1] + lf[m + 1][j]),
            rf[i][j] = min(rf[m + 1][j], a[j] - a[m] + rf[i][m]),
            f[i][j] = min({f[i][m], f[m + 1][j], rf[i][m] + lf[m + 1][j]});
    for (int i = 1; i <= n; ++i)
            cin >> b[i], b[i] += b[i - 1];
    for (int i = 1; i <= n; ++i)
        for (int j = i + 2; j <= n; ++j)
            ans = max(ans, b[j] - b[i - 1] + a[j] - a[i - 1] - f[i + 1][j - 1]);
    cout << ans;
    return 0;
}

赛前发题解，RP++。