设\(f[i][j=0/1]\)表示涂到第\(i\)位，且第\(i\)为颜色为\(j\)，则考虑用\(i\)之前能和\(i\)匹配的位置\(p\)进行转移。\(p\)需要满足下面的条件：
- \(a[p]=a[i]\)。
- \(p\)的颜色为\(j\)。
- \([p+1,i-1]\)之间的颜色全不为\(j\)。
显然，我们只需要找满足条件的最大\(p\)即可，否则答案一定不是最优。所以我们直接维护\(lst[i]=p\)为\(i\)前面满足条件\(1\)的最大，要想满足条件\(3\)，我们还需要维护\(g[l][r]\)表示\(l,r\)这个区间全部同色时，该区间的答案。然后有转移（\(p\neq 0\)时）：
\[f[i][0]=\max(f[i-1][0],f[p+1][0]+a[i]+g[p+1][i-1])\\ f[i][1]=\max(f[i-1][1],f[p+1][1]+a[i]+g[p+1][i-1])\]为什么是\(f[p+1]\)而不是\(f[p]\)？因为如果用\(f[p]\)来转移，就不能制约\([p+1,i-1]\)的颜色和\(i,p\)不同了。
然后可以注意到\(0\)和\(1\)是对称的，所以砍掉第二维是可以的。
点击查看代码
#include<bits/stdc++.h>
#define N 200010
using namespace std;
int t,n,a[N],lst[N],f[N],g[2002][2002];
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>t;
while(t--){
memset(lst,0,sizeof lst);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
g[i][j]=g[i][j-1]+a[j]*(a[j-1]==a[j]);
}
}
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]+g[lst[a[i]]+1][i-1]);
lst[a[i]]=i;
}
cout<<f[n]<<"\n";
}
return 0;
}
时空复杂度都是\(O(n^2)\)的，瓶颈在于预处理\(g\)。不难发现可以只保留\(g[0]\)作为\(sum\)，然后用前缀和的思想，将\(g[x][y]\)转为\(sum[y]-sum[x-1]\)即可。
时空复杂度都为\(O(n)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define V 1000010
#define N 200010
using namespace std;
int t,n,a[N],lst[V],f[N],g[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>t;
while(t--){
memset(lst,0,sizeof lst);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=2;i<=n;i++) g[i]=g[i-1]+a[i]*(a[i-1]==a[i]);
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]+g[i-1]-g[lst[a[i]]]);
lst[a[i]]=i;
}
cout<<f[n]<<"\n";
}
return 0;
}