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

使用前缀和+线性dp解决该问题。

pre[i]前缀和数组 pre[i] = a[1]+...+a[i]

dp[i] 前i个元素的最大得分

pos[x]位置数组 记录数字x最后一次出现的位置

对于每一个位置：

如果a[i]是第一次出现(pos[a[i]]==0)，将a[i]位置记录下来，当前的最大得分不变 dp[i] = dp[i-1]。

如果a[i]是第二次出现，我们就可以得到a[i]的两次pos区间：

1. 选择删除这个区间，得分为区间之前的最大得分 + 区间的和
2. 选择不删除这个区间，得分为区间之前的最大得分

每次选择最优分数，即可保证最后得分最高。

状态转移方程：

dp[i] = max(dp[i-1], dp[pos[a[i]]-1] + (pre[i] - pre[pos[a[i]]-1]));

最后dp[2*n]为结果

#include <iostream>
#include <vector>
using namespace std;

int main() {
    long long n;
    cin>>n;
    vector<long long> a(n*2);
    vector<long long> pre(n*2+2,0);
    vector<long long> dp(n*2+2,0);
    vector<long long> pos(n+1);

    for(int i=1;i<=2*n;i++){
        cin>>a[i];
        pre[i]=pre[i-1]+a[i];
    }

    for(int i=1;i<=2*n;i++){
        if(pos[a[i]]==0){
            dp[i]=dp[i-1];
            pos[a[i]]=i;
        }
        else{
            long long j = pos[a[i]];
            dp[i] = max(dp[i-1], dp[j-1] + (pre[i] - pre[j-1]));    
        }
    }
    cout<<dp[2*n];
}