题解（未完成

来源：题解 P11233 染色 - 洛谷专栏

如果想要两个相同的数对得分作出贡献，就必须满足：

1. 这两个数同色。
2. 这两个数之间的所有数颜色必须和这两个数相反。

如：

3 5 2 5 1 2 1 4

你如果想让两个 $2$ 做出贡献，如果 $2$ 染成红色，那么 $2$ 之间的 $5$ 和 $1$ 就只能染成蓝色。

既然需要将中间的颜色置为同一种颜色，那当 $A_i=A_j$ 时我们可以将 $i+1$ 的位置和 $j-1$ 的位置之间作一条权值 $A_i$ 的边。接下来，我们只需要求交叉的不重合的区间权值和最大值了。如果 $A_i=A_i+1$，则直接将 $A_i$ 加入答案。

例如大样例

5 3 7 2 4 13 11 6 5 5 3 5 12 8 13

解法如下：

最终得分：$18$。

可以证明这可以巧妙解决交叉染色的难题。

求不重复的区间最大权值和很简单，基础 DP 即可。

#include <iostream>
#include <cstdio>
#include <memory.h>
#define int long long
#define ms(a) memset(a, 0, sizeof(a))
using namespace std;
int dp[200005], out[200005], v[200005];
int a[200005], s[200005], mp[1000005];
int n;
void solve(){
	ms(a), ms(dp), ms(s), ms(mp), ms(out), ms(v);
	cin >> n;
	int ans = 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		if(mp[a[i]]){//有相同的数
			if(mp[a[i]] == i - 1) ans += a[i];//如果相邻直接加分
			else out[i - 1] = mp[a[i]] + 1, v[i - 1] = a[i];//否则连边
		}
		mp[a[i]] = i;
	}
	for(int i = 1; i <= n; i++){//求区间最大权值和
		dp[i] = dp[i - 1];
		if(out[i]) dp[i] = max(dp[i], dp[out[i] - 1] + v[i]);
	}
	cout << ans + dp[n] << '\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度：$O(T(N+A_i))$。