题解 | 小红的双排列删除得分

#include <iostream>
using namespace std;

#include<vector>
#include<algorithm>
int main(){
int n;
cin>>n;
vector<int>v(2*n+1);
vector<long long>sum(2*n+1);
vector<vector<int>>pos(n+1);
for(int i=1;i<=2*n;i++){
    cin>>v[i];
    sum[i]=sum[i-1]+v[i];
    pos[v[i]].push_back(i);
}
vector<long long>d(2*n+1);
for(int i=1;i<=2*n;i++){
d[i]=d[i-1];
if(i==pos[v[i]][1]){
    int b=pos[v[i]][0];
    long long s=sum[i]-sum[b-1];
    
    d[i]=max(d[i],d[b-1]+s);
}

}
cout<<d[2*n];
    return 0;
}