2024 染色 · 方案二 last 指针线性 DP

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 1387 字

DP 只依赖上一个同值位置，last 指针线性转移

2024
线性DP

正文

// CSP-S 2024 复赛 T3 · 染色（方案二：last 指针线性 DP，满分 O(n)）
// 原题：https://oj.yecheng.tv/p/ccf-CSPS2024C
// 题意：同方案一（n ≤ 2e5，需满分）。
// 思路（只看"上一个同值位置"）：
//   f[i] = max(f[i-1], f[last-1] + A_i + A_last)，其中 last = i 之前
//   最后一个 A_last == A_i 的位置。为什么只需 last：若 i 与更早的
//   同值位 j 配对而中间还有同值位，把配对换成相邻的 last 不劣
//   （交换论证：中间部分的答案独立可取）。
//   实现：pos[v] = 值 v 上一次出现的位置，扫描时 O(1) 转移。
// 复杂度：O(n)。
// 易错点：
//   1. f[last-1] 不是 f[last]（last 自己的贡献由 +A_last 体现）；
//   2. 不配对的情况 f[i-1] 恒为候选；
//   3. 值域 ≤ 1e6，pos 数组开值域；
//   4. 多组数据重置 pos（只重置出现过的值）。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int T, n;
int A[200005];
long long f[200005];
int pos[1000006];

int main() {
    freopen("color.in", "r", stdin);
    freopen("color.out", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
        for (int i = 1; i <= n; i++) pos[A[i]] = 0;   // 增量重置
        // 注意：先清后用；更稳妥是每组末清
        memset(pos, 0, sizeof(pos));
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= n; i++) {
            f[i] = f[i - 1];
            int last = pos[A[i]];
            if (last) {
                long long cand = f[last - 1] + (long long)A[i] + A[last];
                if (cand > f[i]) f[i] = cand;
            }
            pos[A[i]] = i;
        }
        printf("%lld\n", f[n]);
    }
    return 0;
}

2024 染色 · 方案二 last 指针线性 DP

正文

CSP-S 标程 · 复赛真题的其它内容