真题解析:P11233 [CSP-S 2024] 染色(线性DP·前缀和·桶数组·同色段·最近出现位置)

题目来源：洛谷 P11233 [CSP-S 2024] 染色

题目大意

给定一个长度为 n 的正整数数组 a，你需要把每个位置染成红色或蓝色之一。对每个位置 i，按如下规则计算它的得分 C_i：

• 如果 i 的左侧没有与它同色的数，则 C_i = 0；
• 否则，记 i 左侧与其最靠近的同色位置为 j，若 a_j = a_i，则 C_i = a_i，否则 C_i = 0。

最终得分为所有 C_i 之和，即 ∑C_i。要求最大化最终得分，并输出这个最大值。

直观理解：一个位置 i 想拿到 a_i 分，必须让"左侧最近的同色位置 j"的数值和它相等。也就是说，只有"数值相同且最近的同色邻居"才能带来收益。

输入输出样例

样例输入 #1

331 2 141 2 3 483 5 2 5 1 2 1 4

样例输出 #1

样例解释：

• 第一组数据 [1,2,1]：最优是把第 1、3 个染同色、第 2 个染异色，此时第 3 个最近同色左邻居是第 1 个且数值相等，得 1 分，其余不得分，总分 1。
• 第二组数据 [1,2,3,4]：任意染色都没有"最近同色且数值相等"的位置对，总分恒为 0。
• 第三组数据 [3,5,2,5,1,2,1,4]：最优方案可得 8 分。

数据范围：本题有多组测试数据，组数 T ≤ 10；每组数组长度 n 较大（约 2×10^5 量级）；1 ≤ a_i ≤ 10^6。得分可能很大，需要用 long long 存储。

考点梳理

这道题综合考查了以下知识点，属于典型的"序列上线性 DP + 优化"题型：

• 线性 DP / 序列 DP：按位置从左到右递推，每个位置 O(1) 转移，整体 O(n)。
• 前缀和优化：用前缀和把"一段区间内相邻相等位置的得分"从 O(n) 降到 O(1) 查询。
• 桶 / 值域数组（离散化思想）：用 lst[v] 记录数值 v 上一次出现的位置，按下标 O(1) 访问，等价于对值域做计数/记录。
• 同色段（run）结构分析：把"一段连续同色"作为基本单元，分析段内、段间得分的形成条件。
• 最优性论证：证明"只需考虑数值上一次出现的位置"即可，而不必枚举所有同值位置，是本题思维深度的关键。

解题思路

一、评分规则的本质

位置 i 的得分 C_i 完全由"左侧最近的同色位置 j"决定：j 存在且 a_j = a_i 时得 a_i 分，否则得 0。

换句话说，位置 i 要得分，必须满足两个条件同时满足：

1. i 和它左侧最近的同色位置颜色相同（这是"同色"的题设）；
2. 那个最近同色位置的数值恰好等于 a_i。

如果 i 左侧根本没有同色位置（即 i 是一段同色段的段首），或者最近同色位置的数值不同，i 都拿不到分。

二、同色段（run）结构分析

把同一种颜色连续出现的位置称为一段"同色段"。考察一段同色段内部：

• 段内除段首外，每个位置 i 的"最近同色左邻居"就是 i-1（紧挨着的前一个位置）。
• 因此段内只有"相邻且数值相等"的位置对才能贡献得分：当 a_{i-1} = a_i 时，i 得 a_i 分；否则 i 不得分。
• 段首位置要得分，必须跨过中间一段异色区域，与更前面某段同色的段尾配对（即它最近的同色左邻居在另一段同色段里）。

这带来一个重要观察：相邻且相等的同色位置对是"段内得分"的唯一来源，可以用前缀和统一维护。

三、用前缀和快速求段内相邻相等得分

定义：

s[i] = s[i-1] + (a[i] == a[i-1] ? a[i] : 0)

s[i] 表示前 i 个位置中，"相邻且数值相等"的位置对带来的得分之和。

那么任意区间 (L, R]（左开右闭，即位置 L+1 到 R）内部相邻相等的得分，可以 O(1) 求出：

段内相邻相等得分 = s[R] - s[L]

这个前缀和会在后面的转移中反复用到。

四、状态设计与转移方程

设 dp[i] 表示"前 i 个位置能得到的最大得分"。

对每个位置 i，有两种互斥的染色决策：

转移 A：让 a[i] 自己新开一段（与 a[i-1] 异色）

此时 a[i] 是一段同色段的段首，左侧没有同色位置，所以 a[i] 自身不得分，前 i-1 个位置的最优结构原封不动：

dp[i] = dp[i-1]

转移 B：让 a[i] 得分

记 j = lst[a[i]]，即数值 a[i] 上一次出现的位置（0 表示还没出现过）。

构造方案：把位置 j 和位置 i 染成同一种颜色，把区间 (j, i)（即 j+1 到 i-1）整体染成另一种颜色（成为一整段异色段）。这样：

• 位置 i 的左侧最近同色位置恰好是 j，且 a_j = a_i，所以 i 必得 a_i 分；
• 区间 (j, i) 内部是单色段，其得分就是"相邻且相等"的得分，可用前缀和 O(1) 得到 s[i] - s[j+1]；
• 左侧 [1, j+1] 部分取它自身的最优值 dp[j+1]。

因此：

dp[i] = max(dp[i], dp[j+1] + a[i] + s[i] - s[j+1])   （当 j > 0）

边界细节：当 j+1 == i，也就是 a[i-1] == a[i] 时，上述公式中 (j, i) 区间为空，s[i] - s[j+1] = 0，且 dp[j+1] 此时等于 dp[i-1]，公式退化为 dp[i-1] + a[i]，正好对应"i 直接接在前一段后面、因相邻相等而得分"这一情况。代码里这种自引用的写法天然等价，无需特判。

每个位置取两种转移的最大值即可：

dp[i] = max(dp[i-1], dp[j+1] + a[i] + s[i] - s[j+1])   （j = lst[a[i]]，若 j > 0）

五、为什么只需看上一次出现的位置

直觉上，数值 a[i] 可能在更早的位置 m（m < j）也出现过，要不要枚举所有同值位置？

结论是：只需要考虑最后一次出现的位置 j = lst[a[i]] 就够了。

理由：若 a[i] 要与更靠左的同值位置 m 配对得分，构造方式是把 m 与 i 染同色、把 (m, i) 整体染异色。把配对对象换成更靠右的 j（j 在 m 和 i 之间）后，(j, i) 整体作为异色段仍然合法，且"最近同色左邻居"条件更容易满足；同时换成 j 不会丢掉 j 左侧（包括 m 所在段）的任何结构，因为左侧取的是 dp[j+1]，已经包含了前 j 个位置的最优解。

因此"取最后一次出现位置"一定是不劣的候选，转移中只需维护并查询 lst[a[i]]，不必枚举全部同值位置。

参考代码

#include <bits/stdc++.h>using namespace std;typedef long long ll;int main(){    ios::sync_with_stdio(0);    cin.tie(0);    int t;    cin >> t;    while (t--) {        int n;        cin >> n;        // 原始数据        vector<int> a(n + 1);        int maxa = 0;        for (int i = 1; i <= n; i++) {            cin >> a[i];            maxa = max(maxa, a[i]);        }        // 同色段的得分前缀和：s[i] 记录前 i 个位置中相邻且相等的得分之和        vector<ll> s(n + 1, 0);        for (int i = 2; i <= n; i++) {            s[i] = s[i - 1] + (a[i] == a[i - 1] ? (ll)a[i] : 0);        }        // dp[i]：前 i 个位置的最大得分        vector<ll> dp(n + 1, 0);        // 桶数组，记录每个数值上一次出现的位置，长度为最大值 + 1        vector<int> lst(maxa + 1, 0);        // 线性 DP 递推        for (int i = 1; i <= n; i++) {            // 转移 A：a[i] 自己新开一段（异色），不得分            dp[i] = dp[i - 1];            // 转移 B：a[i] 与上一次出现的同值位置 j 配对得分            int j = lst[a[i]];            if (j > 0) {                ll score = dp[j + 1] + s[i] - s[j + 1] + (ll)a[i];                dp[i] = max(dp[i], score);            }            lst[a[i]] = i;        }        cout << dp[n] << '\n';    }    return 0;}

复杂度分析

• 时间复杂度：对每组数据，预处理前缀和 s 需要 O(n)，DP 递推每个位置 O(1)，故单组 O(n)；全部测试数据总复杂度 O(Σn)。
• 空间复杂度：开了 a、s、dp、lst 四个数组，其中 lst 的长度为值域最大值 maxa + 1，故空间 O(n + maxA)。在 a_i ≤ 10^6 时，lst 约为 10^6 量级，完全可以接受。
• 数据类型：得分可能达到约 2×10^5 × 10^6 = 2×10^11 量级，必须用 long long（文中用 ll 别名）。