2024第二轮CSP-S color

题目链接：Color

首先想到dp

设$ f[i]$为枚举到第 i 位时得分的最大值。

先简单思考一下：

1. 当前 i-1位都没有与$ a[i]$相同的值时，$ f[i]=f[i-1]$。
2. 当$a[i-1]=a[i]$时，要么与 i-1位同一颜色，此时$ f[i]=a[i]+f[i-2]$，要么与 i-1位不同颜色，此时$ f[i]$为$ f[i-1]$

那么当与$ a[i]$相同的不在 i-1位上，而是在 j 位上呢？

此时有两种选择：

1. 左边第一个颜色相同的就是 j 。与 j 位颜色相同，且此时 i 位与 j 位间颜色一样且与 i 位颜色不同
2. 左边第一个颜色相同的不是 j。

设$ g[i][j]$为第 i 位到第 j 位颜色相同时的贡献值。

此时$ f[i]=max(f[i-1],f[j-1]+g[i][j]+a[i])$

注意：j 位为与$a[i]$相同的左侧最靠近$a[i]$的序号，易证明取左侧最靠近的最优。

由于数据范围的限制，$g[i][j]$需用前缀和处理。

由于 j 位颜色不做要求，且 j+1位定与 j 位不同，故可取$f[j+1]+pre[i-1]-pre[j+1]+a[i]$。此时$ f[i+1]$会直接决定 j 位与 j+1位的取值。

由于相等的两数可能相邻，取$f[j+1]+pre[i]-pre[j+1]+a[i]$。

#include<bits/stdc++.h>
#define il inline
using namespace std;
#define int long long
const int N=2e5+5,inf=2333333;
const int M=1e6+5;
int pre[N];
int f[N];
int last[M];
int a[N];
int n;
void init(){
	fill(pre,pre+1+n,0);
	fill(f,f+1+n,0);
	fill(last+1,last+M,0);
	fill(a+1,a+1+n,0);
}
void solve(){
	cin>>n;
	init();
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=2;i<=n;i++){
		if(a[i]==a[i-1]){
			pre[i]=pre[i-1]+a[i];
		}
		else pre[i]=pre[i-1];
	}
	for(int i=1;i<=n;i++){
		f[i]=f[i-1];
		if(last[a[i]]!=0) {
			f[i]=max(f[i-1],f[last[a[i]]+1]+a[i]+pre[i]-pre[last[a[i]]+1]);
		}
		last[a[i]]=i;
	}
	//for(int i=1;i<=n;i++)cout<<f[i]<<' ';
	//cout<<endl;
	cout<<f[n]<<endl;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}