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

#include <iostream>
#include <vector>
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
using ll = long long;
int main() {
    int n; cin >> n;
    vector<ll> a(2*n+5), s(n*2+5), x(n+5), y(n+5), f(n*2+5);
    vector<bool> ed(2*n+5);
    rep(i,1,2*n) cin >> a[i];
    rep(i,1,2*n) s[i] = s[i-1] + a[i];
    rep(i,1,2*n) {
        if(!x[a[i]]) x[a[i]] = i;
        else {
            y[a[i]] = i;
            ed[i] = true;
        }
    }
    rep(i,1,2*n) {
        f[i] = f[i-1];
        if(!ed[i]) continue;
        f[i] = max(f[i], f[x[a[i]] - 1] + (s[y[a[i]]] - s[x[a[i]] - 1]));
    }
    cout << f[2*n] << endl;
}
// 64 位输出请用 printf("%lld")