P11743 Dynamic Array Problem题解

· · 题解

写作原因

一是为社区做贡献，
二是此题很有趣。

题意

题目描述地很详细，就不用复数了。

正解

由于要求一个元素至多被翻转一次，所以本题先可看作从长度为 n 的序列 A 中找出 K 个互不相交的连续字段，将其内部翻转后求最大总贡献。
由于数据范围 n \in [1, 550]，所以可以想到作为 DP 的状态，同时我们可以 O(n ^ 2) 预处理出：

当然，这个值可不能用文中那个公式直接计算，毕竟内部翻转的子段 [l, r] 中间插入某些隔板可能会让值更优，而且不影响除 [l, r] 外的其他子段（内部翻转不影响隔板位置，我们才能先翻转后考虑插入隔板）。

假设选择翻转或不翻转后的子段。

a_l, a_{l + 1}, a_{l + 2},\ldots, a_{r - 2}, a_{r - 1}, a_r

对于这个子段的最大值计算，可以。

从前往后

按照公式，一步步计算。
不过无法考虑中间插板是否有最优。
有 dalao 可以这样考虑最优的话请指教。

从后往前

我们考虑。

所以我们可以推出结论。

X_{i, l, r} = X_{i, l + 1, r} + \sum_{j = l}^{r} a_j

后面的 \sum 可以实时维护。
但如何保证子段的贡献最优呢？
我们可以先将答案更新，然后判断：如果 \sum 的值是负数，就将其置为 0，相当于在这之间插入一块隔板。

证明

a_l, a_{l + 1}, \ldots, a_I, a_{I + 1}, \ldots, a_J, a_{J + 1}, \ldots, a_{r - 1}, a_{r}

设从 a_I 到 a_{J - 1} 之间和为负数，a_{J} 及之后是上一次插板的地方，已经处理过的，那么不在这里插板子的贡献。

X_{i, l, r} = \sum_{i = l}^{I - 1} a_i \times (i - l + 1) + \sum_{i = I}^{J - 1} a_i \times (i - l + 1) + \ldots

在这里插板子的贡献。

X_{i, l, r} = \sum_{i = l}^{I - 1} a_i \times (i - l + 1) + \sum_{i = I}^{J - 1} a_i \times (i - I + 1) + \ldots

其中省略号表示已经处理过的部分。细节后半段，可以看出后者明显更优，因为后者比前者少了这么多：(I - l) \times \sum_{i = I}^{r} a_i。
而又已知 \sum 的部分值为负数，且插入隔板对还未处理过的部分没有影响，所以后者较前者更多。
有个疑问：边界值 a_I 是放在隔板前还是隔板后呢？
答：放在隔板之后。当和累加到 a_I 时突然变成负数，说明 a_I 是个大得不得了的负数，放在隔板之前的话，他在 X_{i, l, r} 中的贡献为 a_I \times (I - l)，放在隔板之后则为 a_I \times 1，明显更大。所以放在隔板之后。

实现：

    for(int i = 1; i <= n; i ++) {
        X[0][i][i] = X[1][i][i] = A[i];

        sum = A[i];
        for(int j = i - 1; j >= 1; j --) {
            sum += A[j];
            X[0][j][i] = X[0][j + 1][i] + sum;
            if(sum < 0) sum = 0;
        }
        sum = A[i];
        for(int j = i + 1; j <= n; j ++) {
            sum += A[j];
            X[1][i][j] = X[1][i][j - 1] + sum;
            if(sum < 0) sum = 0;
        }
    }

预处理完所有子段

考虑 DP。我们设数组 dp_{i, j} 表示在前 i 个元素的序列中翻转 j 次，所得的最大总贡献。
转移如下。

dp_{i, j} = \max(\max_{k = 0}^{i - 1} dp_{k, j} + X_{0, k + 1, i}, \max_{k = 0}^{i - 1} dp_{k, j - 1} + X_{1, k + 1, i})

代码实现：

    for(int i = 0; i <= n; i ++)
        for(int k = 0; k <= K; k ++)
            dp[i][k] = -MX;
    dp[0][0] = 0;
    for(int i = 1; i <= n; i ++) {
        for(int k = 0; k <= min(K, i); k ++) {
            for(int j = 0; j < i; j ++) {
                if(-MX != dp[j][k]) dp[i][k] = max(dp[i][k], dp[j][k] + X[0][j + 1][i]);
                if(k >= 1 && -MX != dp[j][k - 1]) dp[i][k] = max(dp[i][k], dp[j][k - 1] + X[1][j + 1][i]);
            }
        }
    }

最终代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int t = 1;

const int N = 605, MX = 0x3f3f3f3f3f3f3f3f;
int n, A[N], sum;
int K, ans = -MX;

int X[2][N][N], dp[N][N];

void solve() {
    cin >> n >> K;
    for(int i = 1; i <= n; i ++) cin >> A[i];

    for(int i = 1; i <= n; i ++) {
        X[0][i][i] = X[1][i][i] = A[i];

        sum = A[i];
        for(int j = i - 1; j >= 1; j --) {
            sum += A[j];
            X[0][j][i] = X[0][j + 1][i] + sum;
            if(sum < 0) sum = 0;
        }
        sum = A[i];
        for(int j = i + 1; j <= n; j ++) {
            sum += A[j];
            X[1][i][j] = X[1][i][j - 1] + sum;
            if(sum < 0) sum = 0;
        }
    }

    for(int i = 0; i <= n; i ++)
        for(int k = 0; k <= K; k ++)
            dp[i][k] = -MX;
    dp[0][0] = 0;
    for(int i = 1; i <= n; i ++) {
        for(int k = 0; k <= min(K, i); k ++) {
            for(int j = 0; j < i; j ++) {
                if(-MX != dp[j][k]) dp[i][k] = max(dp[i][k], dp[j][k] + X[0][j + 1][i]);
                if(k >= 1 && -MX != dp[j][k - 1]) dp[i][k] = max(dp[i][k], dp[j][k - 1] + X[1][j + 1][i]);
            }
        }
    }

    for(int k = 0; k <= K; k ++) ans = max(ans, dp[n][k]);
    cout << ans;
}

signed main() {
//  freopen("ex_box4.in", "r", stdin);
//  freopen("box.in", "r", stdin);
//  freopen("box.out", "w", stdout);

    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

//  cin >> t;
    while(t --) {
        solve();
    }
    return 0;
}

谢谢。