2024 染色 · 方案一平方 DP

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

O(n^2) 区间 DP 直接转移

2024
线性DP

正文

// CSP-S 2024 复赛 T3 · 染色（方案一：O(n^2) 区间 DP）
// 原题：https://oj.yecheng.tv/p/ccf-CSPS2024C
// 题意：T 组数据，数组 A（长度 n），给每个位置染红/蓝（可全同色）。
//       得分 = 同色内"满足 i<j 且 color_i=color_j=A_i=A_j 的对 (i,j)"
//       的 A_i 之和（每组同色同值对贡献一次 A_i）。求最大总分。
// 思路（区间/线性 DP）：
//   设 f[i] = 前 i 个位置的最大得分（第 i 位与之前某同值同色位配对
//   或新开）。转移：f[i] = max(f[i-1], f[j-1] + A_i + A_j)（j 为 i
//   之前最后一个与 A_i 同值的位置）。O(n^2) 枚举 j：n ≤ 2000 部分
//   分（测试点 1~7 约 10^7·T/10 级别）。
// 复杂度：O(T · n^2)。
// 易错点：
//   1. 配对贡献是 A_i + A_j（两个位置各计一次），不是 2·A_i；
//   2. 同色不同值的相邻对无贡献；
//   3. 多组数据重置数组。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int T, n;
int A[2005];
long long f[2005];

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]);
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= n; i++) {
            f[i] = f[i - 1];
            for (int j = i - 1; j >= 1; j--) {
                if (A[j] == A[i]) {
                    // i 与 j 同色：区间 (j, i) 内不能有 A_k 出现……
                    // 简化口径：中间的同值对另计（官方转移见方案二）
                    long long cand = f[j - 1] + A[i] + A[j];
                    if (cand > f[i]) f[i] = cand;
                }
            }
        }
        printf("%lld\n", f[n]);
    }
    return 0;
}

2024 染色 · 方案一 平方 DP

正文

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

2024 染色 · 方案一平方 DP