P12354题解

· · 题解

不难发现，当区间内 b_i 的值都为 0 时，算出的 v' 才会不为 0，并且修改后 |b_i|=1。而若区间内有一个值不为 0，则那个 |b_i| 一定为 1，则修改无效。

因此我们可以转化题意为：选出若干个互不相交的区间使他们区间和的绝对值之和最大。

通过仔细读题，我们可以发现有一个性质：所有给出的操作区间在还原前互不严格包含。则我们可以通过排序区间来保证 l_i, r_i 都是单调递增的。

我们可以考虑如下 dp 状态：维护区间编号，区间右端点，花费代价，然后暴力去枚举区间移动后的状态，再前缀求 \max 来转移。这样的时间复杂度应该是 O(n^2mk)。

会发现主要花费时间在暴力枚举区间移动后的状态，考虑优化。会发现左端点的位置和右端点的位置是独立的，可以再来一个 dp，维护左端点的位置，花费代价。

具体的，我们可以把第一个 dp 的第一位滚动，设 f_{op, i, j} 为右端点在 i 前，花费代价为 j 的最大值，op 为滚动的标记。再设 g_{i, j} 为区间还未结束，左端点在 i 前，花费代价为 j 的最大值。具体操作看代码。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

inline int max(int x, int y) { return x > y ? x : y; }

struct Node
{
    int l, r;
    bool operator<(const Node &_) const { return l == _.l ? r < _.r : l < _.l; }
}b[MAXN];

int n, m, k;
int a[MAXN];
int g[MAXN][MAXN];     // 区间未结束时，左端点在 i 前, 花费为 j.
int f[2][MAXN][MAXN];  // op: 用于滚动; 右端点在 i 前; 操作次数为 j. 的最大值

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= m; i++) scanf("%d%d", &b[i].l, &b[i].r); 
    sort(b + 1, b + m + 1);
    for(int i = 0; i <= k; i++) g[0][i] = -INF;
    int op = 0;
    for(int cur = 1; cur <= m; cur++, op ^= 1)
    {
        int l = b[cur].l, r = b[cur].r;
        for(int i = 0; i <= n; i++)
        {
            memcpy(f[op^1][i], f[op][i], sizeof(int)*(k+1));
        }
        for(int i = 1; i <= n; i++)
        {
            int dl = abs(i - l), dr = abs(i - r);
            for(int j = 0; j <= k; j++)
            {
                g[i][j] = -INF;
                if(j >= dl) g[i][j] = f[op][i-1][j-dl]+a[i];
                g[i][j] = max(g[i-1][j] + a[i], g[i][j]);
                if(j+dr <= k) f[op^1][i][j+dr] = max(f[op^1][i][j+dr], g[i][j]);
            }
        }
        for(int i = 1; i <= n; i++)
        {
            int dl = abs(i - l), dr = abs(i - r);
            for(int j = 0; j <= k; j++)
            {
                g[i][j] = -INF;
                if(j >= dl) g[i][j] = f[op][i-1][j-dl]-a[i];
                g[i][j] = max(g[i-1][j] - a[i], g[i][j]);
                if(j+dr <= k) f[op^1][i][j+dr] = max(f[op^1][i][j+dr], g[i][j]);
            }
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j <= k; j++)
            {
                f[op^1][i][j] = max(f[op^1][i][j], f[op^1][i-1][j]);
            }
        }
    }
    int ans = -1;
    for(int i = 0; i <= k; i++) ans = max(ans, f[op][n][i]);
    printf("%d", ans);

    return 0;
}