题解：P11233 [CSP-S 2024] 染色

· · 题解

这篇题解的做法是作者在考场上想的思路的完善（虽然场上没做出来）。

考场思路

在考场上，作者先很快地设出了状态：dp_i 表示 A_1 到 A_i 能产生的最大贡献。然后，作者认为每一个 i 可以由左边距它最近的满足 A_j=A_i 的 j 转移，只需加上区间 [j+1,i-1] 全部染成同色的贡献即可。

然而，写到一半，作者发现不对劲，然后发现了以下两个问题：

然后场上就放弃了，打了暴力。

可是回家路上，作者很快就想出了一些方法来规避这两个问题：

正确思路

容易发现，如果存在一段连续的区间 [l,r] 满足 A_l,A_{l+1},\dots,A_r 都相同，那么这一段区间肯定全部染成同色最优。于是考虑先将这种同色区间缩成一个点，并记录这个点的加权 w_l=r-l+1。这样，最后的结果加上 \sum_{i=1}^mA_i(w_i-1) 即可（其中 m 表示缩完点后的数组大小）。

为什么要这么操作？主要是为了方便转移，这样染成同的一段区间，除了第一个数都没有贡献了。

设计状态 dp_{i,0/1}。dp_{i,0} 表示 A_1 到 A_i 能产生的最大贡献，dp_{i,1} 表示：保证 A_{i+1} 能产生贡献的前提下，A_1 到 A_i 能产生的最大贡献。

为什么会想到这个状态呢？因为作者在考场上碰到的第二个问题，A_{j+1} 的贡献无法确定。而现在这个贡献就可以确定了。dp_{j,0} 就没有贡献，dp_{j,1} 就有贡献。

现在设计转移方程如下：

dp_{i,0}=\max(dp_{i-1,0},dp_{i-1,1}+a_i) dp_{i,1}=\begin{cases}\max(dp_{pre_{i+1},0},dp_{pre_{i+1,1}}+a_{pre_{i+1}+1}),pre_{i+1}\ne 0\\-\infty,pre_{i+1}=0\end{cases}

其中，pre_i 表示最大的满足 A_j=A_i 的 j，若不存在则为 0。

这个转移方程式十分就好理解的。不理解的可以反复看几遍状态的叙述。

这样就做完了，复杂度 O(Tn)。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn = 2e5 + 5, maxv = 1e6 + 5;

ll a[maxn], cnt[maxn], dp[maxn][2];
int pv[maxv], pre[maxn];

int main(){
    int T;
    scanf("%d", &T);
    while(T --){
        int n;
        scanf("%d", &n);
        for(int i = 1; i <= n; i ++){
            scanf("%d", &a[i]);
            if(a[i] == a[i - 1]) cnt[i - 1] ++, i --, n --;
        }
        ll sum = 0;
        for(int i = 1; i <= n; i ++) pre[i] = pv[a[i]], pv[a[i]] = i, sum += a[i] * cnt[i];
        dp[0][0] = 0, dp[0][1] = -(ll)1e18;
        for(int i = 1; i <= n; i ++){
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + a[i]);
            dp[i][1] = -(ll)1e18;
            if(pre[i + 1]) dp[i][1] = max(dp[pre[i + 1]][0], dp[pre[i + 1]][1] + a[pre[i + 1] + 1]);
        }
        printf("%lld\n", dp[n][0] + sum);
        for(int i = 1; i <= n; i ++) pv[a[i]] = cnt[i] = pre[i] = dp[i][0] = dp[i][1] = 0;
    }
    return 0;
}