還記得當(dāng)時(shí)在考場(chǎng)上看到這個(gè)題內(nèi)心是痛苦的，想著騙一騙分，但是我當(dāng)時(shí)根本不知道動(dòng)態(tài)規(guī)劃是什么，所以沒能做出來。

今天重看，發(fā)現(xiàn)一個(gè)很強(qiáng)的解法，甚至是來自 JY 中學(xué)的，這不得不整理一下了。

做法。

采取最簡單的狀態(tài)設(shè)計(jì)，設(shè) \(dp[i]\) 為考慮到第 \(i\) 位的答案。

我們每一次固然是從上一次當(dāng)前值出現(xiàn)的地方進(jìn)行轉(zhuǎn)移。

我們用 \(last[a[i]]\) 表示 \(i\) 的上一個(gè)位置。

我們需要讓這個(gè)位置和當(dāng)前位置顏色一樣，中間的地方都是另外一個(gè)顏色的。

中間這一部分只有相鄰相等的才能貢獻(xiàn)。

所以不難列出來式子。

\(f_i=max_{i=1}^{n}(f_{last[a_i]+1}+a_i+sum[i]-sum[last[a_i]])\)

sum 就是相鄰相等的前綴和

代碼

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=1e6+116;
int dp[MN], last[MN], sum[MN];
int n, a[MN], T;
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>T; while(T--){
		memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp));
		memset(last,0,sizeof(last)); memset(sum,0,sizeof(sum));
		cin>>n; for(int i=1; i<=n; ++i) cin>>a[i];
		for(int i=2; i<=n; ++i) sum[i]=(a[i]==a[i-1]?sum[i-1]+a[i]:sum[i-1]);
		for(int i=1; i<=n; ++i){
			dp[i]=dp[i-1];
			if(last[a[i]]) dp[i]=max(dp[last[a[i]]+1]+a[i]+sum[i]-sum[last[a[i]]+1],dp[i]);
			last[a[i]]=i;
		}
		cout<<dp[n]<<'\n';		
	}
	return 0;
}