P11233 [CSP-S 2024] 染色 题解

· · 题解

这题暴力 DP 方法很多，自然解法也很多。

这个可能是代码最短和最易懂的解法，但是这个唐龙仍然在考场上写了 2h。

考虑暴力 DP，设 f_{i,j,k} 为已经填完了前 i 个数，上一个染红的数值为 j，染蓝的数值为 k，此时最大得分。特别的 f_{i,0,0} 表示还没有红色的数和蓝色的数。

转移显然。注意到很多有用的性质。

  1. 由于转移方程，我们能轻松消掉第一维，接下来只考虑后两维。

  2. 由于每个数必须染色，所以每次转移后，整个 DP 数组只有一列和一行是可能有值的，可以只维护这一行和这一列。

  3. 对于一种方案，我们可以将染的色反转，答案不变，所以 DP 数组有对称性，即 f_{i,j}=f_{j,i}，所以现在只用考虑一行或一列了。

现在能尝试快速简单的维护 DP 了，设维护的这一行值为 g。

考虑从上次 DP 转移过来，设上个元素为 x，当前元素为 y，由于除了 f_{x,i} 和 f_{i,x}，其他元素都是没有值的，所以当前元素要加的地方有值的只有两个，还是对称的。加完之后，f_{i,y} 和 f_{y,i} 还要与 DP 数组的其它位置取最大值，但由于有值的地方就那些，所以取完之后，g 中除了 g_x 和 g_y，其他地方不变。设之前 g 的最大值为 p，则 g_x=\max(p,g_y+y)，在这之后，g_y=-Inf。

若当前值与上个值相同，重叠的元素就有很多个，没法放在一起讨论。于是干脆特判，加进 add 里面，DP 完再加上，一起输出。

于是做完了，码（非赛时）：

#include<stdio.h>
const int MaxN=200000,MaxV=1000000;
const long long Inf=1e13;
int T,n,a[MaxN+1];
long long f[MaxV+1];
#define Max(a,b) (a>b?a:b)
signed main(){
    scanf("%d",&T);
    while(T--){
        long long mxf=0,add=0,v=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",a+i),v=Max(v,a[i]);
        for(int i=1;i<=v;i++)f[i]=-Inf;
        f[0]=0;
        for(int i=1;i<=n;i++)
            if(a[i-1]==a[i])
                add+=a[i];
            else
                f[a[i-1]]=mxf=Max(f[a[i]]+a[i],mxf),f[a[i]]=-Inf;
        printf("%lld\n",mxf+add);
    }
}