P11233 染色

本文是对 P11233 [CSP-S 2024] 染色题解的详细解释。

题意简述

给定一个长度为 $n$ 的正整数数组 $A$ ，其中所有数从左至右排成一排。

你需要将 $A$ 中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分：

设 $C$ 为长度为 $n$ 的整数数组，对于 $A$ 中的每个数 $A_i$ （ $1 \leq i \leq n$ ）：

如果 $A_i$ 左侧没有与其同色的数，则令 $C_i = 0$ 。
否则，记其左侧与其最靠近的同色数为 $A_j$ ，若 $A_i = A_j$ ，则令 $C_i = A_i$ ，否则令 $C_i = 0$ 。

你的最终得分为 $C$ 中所有整数的和，即 $\sum \limits_{i=1}^n C_i$ 。你需要最大化最终得分，请求出最终得分的最大值。

范围： $1\le n\le2\times10^5,1\le A_i\le1\times10^6$ 。

思路：DP 状态设计

我们从 i=1 遍历到 i=n。先考虑最简单的状态设计： $dp[i]$ 即表示给 $A_1\to A_i$ 染色得到的最大得分， $dp[n]$ 即最终答案。

那么如何递推？假设我们现在遍历到了 $A_i$ ，我们如何给这个点染色？依题意，我们找到最后一个和 $A_i$ 数值相同的数，不妨记为 $A_k$ 。

如果我们令 $A_i$ 与 $A_k$ 颜色相同，则得分为 $dp[k+1]+s_{k+1,i}+A_i$ ，这里的 $s_{k+1,i}$ 指的是把 $A_{k+1}\to A_i$ 染成同一个颜色（当然是异于 $A_k$ 和 $A_i$ 的颜色）能得到的分数。

至于为什么是 $dp[k+1]$ 而不是 $dp[k]$ 呢？因为 $s_{k+1,i}$ 实际上计算的是 $A_{k+2}\to A_i$ 贡献的得分（不包含 $A_{k+1}$ 的贡献，因为它的前一位 $A_{k}$ 不在范围中）。而我们统计分数需要不重不漏，即 $A_{k+1}$ 的贡献也要统计。

现在我们聚焦如何快速找到 $A_k$ 、如何快速求出 $s_{k+1,i}$ ：

对于 $A_k$ ，我们维护一个数组 $last[x]$ ，表示最后一个等于 $x$ 的数出现的位置。递推时只需要更新 $last[A_i]\gets i$ 即可，于是 $k=last[A_i]$ ，我们在递推时可以 $O(1)$ 求出 $A_k$ 。
对于 $s$ ，我们考虑维护前缀和。为什么？因为既然我们染成同一个颜色，那么一个数字（假设是 $A_n$ ）是否对得分有贡献，仅取决于它的前一个数 $A_{n-1}$ ，如果 $A_{n-1}=A_n$ ，就会贡献 $A_n$ 个得分。显然 $s$ 是可差分的。我们在 DP 之前预处理 $s[]$ ，只需要 $O(n)$ 的时间复杂度。

综上，本解法的时间复杂度为 $O(n)$ ，可以通过本题。

状态转移方程见下一小节。

编码

注意代码第 28 行，我调了很久，这里有个坑：

k = last[A[i]];
if (k) { // 如果 A[i] 出现过
    if (k == i - 1) dp[i] = dp[i - 1] + A[i];
    else dp[i] = max(dp[i - 1], dp[k + 1] + A[i] + s[i] - s[k + 1]);
} else {
    dp[i] = dp[i - 1];
}

当 $k=i-1$ 时，我们试着计算高亮下一行，max() 的第二个参数为 $dp[i]+A_i$ 。然而很不幸的是，此时 $dp[i]=0$ ，因为它没被设置过。但实际上我们想要的是 $dp[i-1]+A_i$ 。我参考的题解是这样写的：

dp[i] = dp[i - 1], k = last[A[i]];
if (k) { // 如果 A[i] 出现过
    dp[i] = max(dp[i - 1], dp[k + 1] + A[i] + s[i] - s[k + 1]);
}

注意到高亮行之前 $dp[i]$ 已经被设置过了，所以很巧地避开了这个坑（感觉原题解的转移方程就没写对）。

完整的转移方程：

dp[i]= \begin{cases} dp[i-1] & k=0, \\ dp[i-1]+A_i & k=i-1,\\ \max\{dp[i-1],dp[k+1]+A[i]+s_i-s_{k+1}\} & \text{otherwise}.\\ \end{cases}

用时 1.16 s 内存 12.84 MB

/*
* P11233 [CSP-S 2024] 染色
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5, MAXM = 1e6;
long long  T, n, k;
long long A[MAXN + 1], dp[MAXN + 1], last[MAXM + 1], s[MAXN + 1];

int main() {
    cin >> T;
    while (T--) {
        ios::sync_with_stdio(false);
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> A[i];
        // 多测清空
        memset(dp, 0, sizeof(dp));
        memset(last, 0, sizeof(last)); // last[x] = 0 表示 x 没出现过
        memset(s, 0, sizeof(s));
        for (int i = 2; i <= n; i++) { // 预处理 s[]
            if (A[i] == A[i - 1]) s[i] = s[i - 1] + A[i];
            else s[i] = s[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            k = last[A[i]];
            if (k) { // 如果 A[i] 出现过
                if (k == i - 1) dp[i] = dp[i - 1] + A[i];
                else dp[i] = max(dp[i - 1], dp[k + 1] + A[i] + s[i] - s[k + 1]);
            } else {
                dp[i] = dp[i - 1];
            }
            last[A[i]] = i;
        }
        cout << dp[n] << '\n';
    }
    return 0;
}

⭐ 学到了什么？

设计 DP 状态时，不妨 “返璞归真”，不要乱想。应该先从最容易想到的状态开始，如果其不能满足解题的要求，再有针对地克服缺点，设计新的状态。

（大概是这样）

题意简述​

思路：DP 状态设计​

编码​

⭐ 学到了什么？​

题意简述

思路：DP 状态设计

编码

⭐ 学到了什么？