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

#include <bits/stdc++.h>
using namespace std;

struct nod {
    int fir;  // 数字第一次出现的位置
    int sec;  // 数字第二次出现的位置
    // 带默认参数的构造函数
    nod(int f = 0, int s = 0) : fir(f), sec(s) {}
};

int main() {
    int n;
    cin >> n;
    int len = 2 * n;
    vector<int> arr(len + 1);       // 存储原始数组（1-based）
    vector<long long> pre_sum(len + 1, 0);  // 前缀和数组，用long long防止溢出
    vector<nod> pos(len + 1);       // pos[x] 存储数字x的第一次/第二次出现位置
    vector<long long> dp(len + 1, 0); // dp[i] 表示前i个位置能得到的最大和

    // 1. 读取数组并构建前缀和、记录每个数字的位置
    for (int i = 1; i <= len; ++i) {
        cin >> arr[i];
        pre_sum[i] = pre_sum[i - 1] + arr[i]; // 计算前缀和
        int x = arr[i];                       // 当前位置的数字值
        if (pos[x].fir == 0) {
            pos[x].fir = i; // 第一次出现，记录位置
        } else {
            pos[x].sec = i; // 第二次出现，记录位置
        }
    }

    // 2. 动态规划计算最大和
    for (int i = 1; i <= len; ++i) {
        // 情况1：不选第i个位置，最大和等于dp[i-1]
        dp[i] = dp[i - 1];
        
        // 情况2：如果i是某个数字的第二次出现位置，尝试选这个区间
        int x = arr[i];
        if (pos[x].sec == i) { // 确认i是数字x的第二次出现位置
            int first = pos[x].fir; // 数字x第一次出现的位置
            // 选这个区间的和 = 前first-1个位置的最大和 + 该区间的和
            long long sum = dp[first - 1] + (pre_sum[i] - pre_sum[first - 1]);
            dp[i] = max(dp[i], sum); // 取两种情况的最大值
        }
    }

    // 输出前2n个位置的最大和
    cout << dp[len] << endl;
    return 0;
}