P11233 [CSP-S 2024] 染色 题解

· · 题解

本文于作者高考后进行了重构与补充进行重新讲解，原题解内容链接如下。

设 f_i 表示考虑到第 i 位的答案。具体的，其定义为，考虑计算范围为 [1,i]，与 a_i 完全相同的末尾若干个数强制视作一段的开头，该情况下的最佳收益。显然的，对于每一个位置 i 可以令 f_i = f_{i-1}。用 lst_i 记录 i 上一次出现的位置，初始化令所有的 lst_i = 0，每遍历到一个位置，动态更新 lst_{a_i} = i。然后枚举区间更新 f_i，也可以预处理出来一个 g 数组辅助转移，复杂度 O(n^2)。使用前缀和优化，每当 a_i=a_{i-1} 时，更新前缀和数组 s_i。最后对于 a_i 如果 lst_{a_i} 存在，对于 f_i 的转移为：

f_i=\max_{i=1}^{n}\{f_{lst_{a_i}+1}+a_i+s_i-s_{lst_{a_i}}\}

最终的答案为 f_n，复杂度 O(n)。

当然，本文在初次发布后有很多人提出了一些关于正确性的问题，这里感谢 @syksykCCC 哥哥进行的补充。以下内容是 @syksykCCC 补充的一些关于正确性的一些分析证明。

我们前面提到了，f_i 表示考虑到第 i 位的答案。具体的，其定义为，考虑计算范围为 [1,i]，与 a_i 完全相同的末尾若干个数强制视作一段的开头，该情况下的最佳收益。比如 a_i=p，那 f_i 描述的分段就是形如 a_1,a_2,⋯,a_{i−k},p,p,⋯,a_i=p 其中 p∈[1,i-1]。下面是对做法与描述匹配解释。首先 a_i=a _{i−1} 时，最优方案肯定是 i 继承 i−1 的颜色，所以程序按上述即 f_i=f _{i−1}+a _i，把相同的一段数缩点，不妨设相邻的两个数不同。 f_i 代表 i 恰好是新一段的开头，i−1 是上一段的结尾。

还有一个问题，就是转移方程中所调用的下标是 lst_{a_i}+1。其实本人第一次做的时候一直过不了，后来就开始试，比如调调下标，发现 lst_{a_i} 过不了，然后改成 lst_{a_i}+1 过了，所以就这么写了，并没有多想。现在，我们来对这个问题进行详细补充。

首先就是，当 a_i 产生贡献时，那么与 a_i 匹配找 lst_{a_i} 的值，比如你 a_{lst} 与 a_i 为蓝色，那么下标从 lst_{a_i}+1 到 i-1 为红色。则转移需要的显然为 f_{lst_{a_i}+1} 的。如若不然，那么就往前找到这个可以匹配的值，假设找的下标为 j，那么 a_j 自然仍为蓝，但是 a_{lst_{a_i}} 要调蓝。则只改变 a_{lst_{a_i}} 的颜色，实现了收益最大。

如果 a_i 不产生贡献，那么 f_{i-1} 为目标答案。按照刚才对 f_i 的定义，i-1 独立成段。接下来，我们来分析为何最优方案如此。比如你 a_{j} 与 a_i 为蓝色（j<i 并且二者差值相当大，即该段很长），下标从 j+1 到 i-1 为红色。将 a_i 与 a_{i-1} 的颜色进行调换，显然答案不会变劣。因为 a_{i-1} 与 a_i 本身不可能有贡献，而进行调整后则有可能使其答案变优，所以 i-1 能独立成段。

答案输出 f_n，则为上述 a_i 不产生贡献的假设的类比，显然有 a_n 独立成段，答案更优秀。则上述做法具有正确性，论证结束。

最后，非常感谢 @syksykCCC 和 @hanss6 的补充，本篇题解的诞生与完善离不开二人的帮助。

代码如下

#include <bits/stdc++.h>
#define int long long
#define m(a) memset(a, 0, sizeof a)

using namespace std;

const int N = 1e6 + 5;

int n, T, a[N], lst[N], f[N];
int s[N], ans; 

signed main() 
{
    cin >> T;
    while (T--) 
    {
        cin >> n; m(a), m(lst), m(f), m(s);
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 2; i <= n; i++) s[i] = (a[i] == a[i - 1] ? s[i - 1] + a[i] : s[i - 1]);
        for (int i = 1; i <= n; i++) 
        {
            f[i] = f[i - 1];
            if (lst[a[i]]) f[i] = max(f[i], f[lst[a[i]] + 1] + a[i] + s[i] - s[lst[a[i]] + 1]);
            lst[a[i]] = i;
        }
        cout << f[n] << endl;
    } 
    return 0;
}