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

的最大值。具体操作看代码。

CPP

#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;
}

文章操作

相关推荐

评论

P12354题解