还记得当时在考场上看到这个题内心是痛苦的，想着骗一骗分，但是我当时根本不知道动态规划是什么，所以没能做出来。
今天重看，发现一个很强的解法，甚至是来自 JY 中学的，这不得不整理一下了。
做法。
采取最简单的状态设计，设 \(dp[i]\) 为考虑到第 \(i\) 位的答案。
我们每一次固然是从上一次当前值出现的地方进行转移。
我们用 \(last[a[i]]\) 表示 \(i\) 的上一个位置。
我们需要让这个位置和当前位置颜色一样，中间的地方都是另外一个颜色的。
中间这一部分只有相邻相等的才能贡献。
所以不难列出来式子。
\(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;
}