秋殇别恋题解

船酱魔王 · 2025-03-09 12:36:57 · 题解

题意回顾

有长度为 n 的序列 a,b ，对于 1 \le i \le n ， a_i 的值给定， b_i 初始时均为 0 。你需要支持以下操作 m 次：

l r v 表示先算出 v'=v(1-\max_{i=l}^r|b_i|) ，对于 l \le i \le r ， b_i \leftarrow b_i+v' 。

你知道这道题的 a 数组，每次操作的区间范围，但忘记了操作的相对顺序和操作参数（只能取值 -1 或 1 ），你可以移动区间端点一个单位长度消耗 1 代价，请用不超过 k 代价还原数据最大化输出结果。

数据范围： 1 \le n \le 1000 ， 1 \le m \le 100 ， 0 \le k \le 1000 ， |a_i| \le 10^6 。

分析

算法 1

暴力枚举 m! 种操作顺序，然后在枚举顺序的时候枚举每个区间的最终样态，时间复杂度难以想象。

期望得分 10 分。

算法 2

考虑转化题意，每次操作前 |b_i| \le 1 ，则 v' 在区间内 b_i 非全 0 时必然为 0 ，否则等效于区间赋值，因为 |v| \le 1 得到操作后必然仍有 |b_i| \le 1 ，故每次操作都是判断区间和之前操作区间是否有交，无交才赋值。然后互不相交的区间显然是互相独立的，对答案取最优贡献就是绝对值，转化题意为选出若干个区间互不相交使得他们的绝对值之和最大。

故双关键字排序区间后，设计以最靠右一个被选中区间右端点为状态的动态规划，使用前缀 \max 优化转移即可。时间复杂度为 O((4m)^kn) 。

期望得分 25 分。

算法 3

因为选择区间的顺序无关紧要，我们只关心那些位置 b_i 非 0 和已经消耗的区间移动代价，依照以上要关心的状态量进行设计状态压缩动态规划，时间复杂度为 O(nmk2^n) 。

期望得分 15 分，可以结合其他算法来得到 40 分。

算法 4

根据区间互不严格包含的性质，若 l_i < l_j 则 r_i \le r_j ，则可以通过排序区间使得 l_i,r_i 均单调不降。

然后考虑根据排序不等式，靠左的区间必然要移动到相对靠左的位置。所以排序区间后后必然可以保证每个区间只被转移一次且移动后右端点单调不降，故维护右端点、当前区间编号、区间移动代价作为 DP 的状态即可。

每次暴力枚举区间移动后样态，然后使用前缀 \max 优化转移，时间复杂度为 O(n^2mk) 。

期望得分 55 分，可以结合其他算法来得到 70 分高分。

算法 5

感觉 DP 的状态难以优化，但是暴力枚举区间移动后样态太暴力了！考虑优化掉。

我们发现区间左右端点是独立的，故建立内层 DP 数组，把区间左端点计入移动代价和右端点计入移动代价分开，然后中间区间元素分别计入答案就行。需要拆开绝对值符号正负算两次。

时间复杂度 O(nmk) ，期望得分 100 分。

标程

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1005;
const int inf = 1e9 + 5;
int n, m, k;
int a[N];
int dp[2][N][N];//fg=0/1区间号，前缀长度<=i，操作次数=j
int fp[N][N];//区间未结束，左端点花费记录，钦定正负 
struct node {
    int l, r;
    bool operator<(node p1) {if(l != p1.l) return l < p1.l; return r < p1.r;}
} b[N];
inline int getabs(int x) {return (x <= 0) ? (-x) : x;}
inline int gmax(int x, int y) {return (x <= y) ? y : x;}
int main() {
    if(k <= 1)
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) {
        cin >> b[i].l >> b[i].r;
    }
    sort(b + 1, b + m + 1);
    int fg = 0;
    for(int j = 0; j <= k; j++) fp[0][j] = -inf;
    for(int round = 1; round <= m; round++) {
        int l, r;
        l = b[round].l, r = b[round].r;
        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= k; j++) dp[fg ^ 1][i][j] = dp[fg][i][j];
        }
        for(int i = 1; i <= n; i++) {
            int il = getabs(i - l);
            int ir = getabs(i - r);
            for(int j = 0; j <= k; j++) {
                fp[i][j] = gmax((j >= il) ? (dp[fg][i - 1][j - il] + a[i]) : (-inf), fp[i - 1][j] + a[i]);
                if(j + ir <= k) dp[fg ^ 1][i][j + ir] = gmax(dp[fg ^ 1][i][j + ir], fp[i][j]);
            }
        }
        for(int i = 1; i <= n; i++) {
            int il = getabs(i - l);
            int ir = getabs(i - r);
            for(int j = 0; j <= k; j++) {
                fp[i][j] = gmax((j >= il) ? (dp[fg][i - 1][j - il] - a[i]) : (-inf), fp[i - 1][j] - a[i]);
                if(j + ir <= k) dp[fg ^ 1][i][j + ir] = gmax(dp[fg ^ 1][i][j + ir], fp[i][j]);
            }
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= k; j++) {
                dp[fg ^ 1][i][j] = gmax(dp[fg ^ 1][i][j], dp[fg ^ 1][i - 1][j]);
            }
        }
        fg ^= 1;
    }
    int ans = -1;
    for(int j = 0; j <= k; j++) ans = gmax(ans, dp[fg][n][j]);
    cout << ans << endl;
    return 0;
}

秋殇别恋 题解