相当巧妙的优化。

首先我们需要设计一下状态，一般而言，我们会设考虑到 $i$，的答案为 $f(i)$。

然而我们可以作出更精细的限制，我们可以令 $i$ 与 $i-1$ 异色。

首先比较显然的，可以转移 $f(i) = f(i-1)$。

剩下的转移想要优于 $f(i-1)$，$i$ 必须做贡献。

记 $lst(a(i))$ 表示 $a(i)$ 上一次出现的位置。

那么我们只可能从 $lst(a(i))+1$ 转移过来，因为其他的位置一定不如它优。

同时我们 $[lst(a(i))+1,i]$ 中间的贡献用前缀和 $s$ 来维护。

那么我们有转移：$f(i) = f(lst(a(i))+1) + a(i) + s(i) - s(lst(a(i))+1)$。

答案 $f(n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6;
int n;
int a[maxn+5];
int f[maxn+5];
int s[maxn+5];
int lst[maxn+5];
inline void Solve(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        if(1<i) s[i]=s[i-1]+(a[i]==a[i-1])*a[i];
    }
    memset(lst,0,sizeof(lst));
    for(int i=1;i<=n;i++){
        f[i]=f[i-1];
        if(lst[a[i]])
            f[i]=max(f[i],f[lst[a[i]]+1]+a[i]+s[i]-s[lst[a[i]]+1]);
        lst[a[i]]=i;
    }
    printf("%lld\n",f[n]);
}
signed main(){
    int tcnt;scanf("%lld",&tcnt);
    while(tcnt--) Solve();
    return 0;
}