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

silverleo · 2025-01-17 14:14:18 · 题解

思路比较简单，想完之后都怀疑自己想岔了，好歹是蓝题。

思路

先观察，容易发现想要结果最大，连续的相同数字一定是涂同色的，所以可以先预处理把连续的相同数字合并成一个，并将贡献的得分计算好。

然后得到一个任意相邻位置都不等的数列 a。设 D_i 为在位置 i 能取到的最大得分，对于任意一个位置 a_i，都有放弃和得分两种情况:

• 放弃 a_i 很简单，就直接取前一个位置的最大得分 D_{i-1} 就行了
• 想要得分，先找到值 a_i 在之前出现的最后位置 j (a_j=a_i,1 \le j<i)，这时需要满足条件：

这意味着 j 到 i 之间只有 a_{j+1} 有可能得分，其他位置都不可能得分，所以位置 i 得分只需要在 D_{j+1} 基础上加上值 a_i 就可以了。

最终 D_i=\max(D_{i-1},D_{j+1}+a_i)，复杂度 O(n)。

代码

#include<bits/stdc++.h>
using namespace std;
int T,n,A,last[1000005],pre[200005];
long long a[200005],dp[200005];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        memset(last,0,sizeof(last));
        int len=0;
        long long sum=0;
        for(int i=1;i<=n;i++){
            cin>>A;
            if(A==a[len]){//合并连续相同值
                sum+=A;
            }else{
                a[++len]=A;
                pre[len]=last[A];
                last[A]=len;
            }           
        }
        for(int i=2;i<=len;i++){
            dp[i]=pre[i]?max(dp[pre[i]+1]+a[i],dp[i-1]):dp[i-1];
        }
        cout<<sum+dp[len]<<endl;
    } 
}