CSP-S2024 T3 题解

StayAlone · 2024-10-27 10:38:02 · 题解

设 lst_i 表示最大的 j 满足 j<i\land a_j=a_i。

第一个重要观察：若 C_i\ne 0，则一定有 lst_i 是最近的与 i 颜色相同的位置。

证明考虑，若存在 i < j < k，使得 a_i=a_j=a_k，而与 k 最近的与之颜色相同的是 i，容易通过调整使得 C_j,C_k 均不为 0。

其次可以发现，若 a_i=a_{i+1}，则最优解中 C_{i+1}\ne 0。更精准的说法是，若存在一个染色方案使得 C_{i+1}=0，则一定能通过调整，使得原本不等于 0 的仍不等于 0，且 C_{i+1}\ne 0。

那么不考虑 lst_i=i-1 的 i，将 [lst_i, i] 看作一条带权值的线段。一个线段集合存在对应的染色，当且仅当两两线段的交的长度小于 2。简单分类讨论即可证明。

问题转化为，求一个合法的线段集合，使其权值和尽量大。

那么有一个很不牛的 dp。设 f_{i} 表示只考虑前 i 个数（线段）的最大权值和。显然有 f_{i} = \max\{f_{i-1}, a_i + f_{lst_i+1}\}。

洛谷民间数据过了。

int n, a[MAXN], lst[MAXN * 5];
ll f[MAXN];

int main() {
    for (int T = read(); T--; ) {
        read(n); rer(i, 1, n, a);
        ll sum2 = 0;
        rep1(i, 1, n) {
            f[i] = f[i - 1];
            if (lst[a[i]]) {
                int l = lst[a[i]], r = i;
                if (r - l == 1) sum2 += a[i];
                else gmax(f[i], f[l + 1] + a[r]);
            } lst[a[i]] = i;
        } printf("%lld\n", f[n] + sum2);
        rep1(i, 1, n) lst[a[i]] = 0;
    }
    return 0;
}