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

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

思路

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

然后得到一个任意相邻位置都不等的数列

a

。设

D_i

为在位置

i

能取到的最大得分，对于任意一个位置

a_i

，都有放弃和得分两种情况:

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

$a_i$ ， $a_j$ 同色
$j$ 到 $i$ 之间（不含 $j$ 、 $i$ ）的颜色相同，且都与 $a_i$ 、 $a_j$ 不同

这意味着

j

到

i

之间只有

a_{j+1}

有可能得分，其他位置都不可能得分，所以位置

i

得分只需要在

D_{j+1}

基础上加上值

a_i

就可以了。

最终

D_i=\max(D_{i-1},D_{j+1}+a_i)

，复杂度

O(n)

。

代码

CPP

#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;
	} 
}

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

文章操作

思路

代码

相关推荐

评论

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