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

前面的大佬竟然一句话都没有说，直接发代码了，对蒟蒻（包括我）有点不友好，所以我来发一个带讲解的版本awa

代码里说的很明白啦，再有不会的可以评论区问（喜欢的话请点个赞支持一下吧）

#include <bits/stdc++.h>
using namespace std;
#define sc second
#define fr first
#define int long long
const int mod = 998244353;
int n, m, num, cnt = 0, l = 1, r = 1e10;
string s;

void _()
{
    cin >> n;
    vector<int> a(2 * n + 5);
    vector<int> q(2 * n + 5);   // 前缀和数组
    vector<int> start(2 * n + 5);  // 记录每个数字第一次出现的位置
    vector<int> dp(2 * n + 5); // dp数组：到位置i为止的最高得分

    for (int i = 1; i <= 2 * n; i++)
    {
        cin >> a[i];
        q[i] = q[i - 1] + a[i]; // 计算前缀和

        if (start[a[i]]) // 如果这个数字之前出现过（现在是第二次出现）
        {
            // 选择删除以这对数字为端点的区间
            // dp[start[a[i]] - 1]: 在这个区间开始之前的最佳得分
            // q[i] - q[start[a[i]] - 1]: 这个区间的和
            dp[i] = dp[start[a[i]] - 1] + q[i] - q[start[a[i]] - 1];
        }
        else
        {
            start[a[i]] = i; // 记录第一次出现的位置
        }

        // 不选择以当前位置为右端点的区间
        dp[i] = max(dp[i], dp[i - 1]);
    }
    cout << dp[2 * n] << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int awa = 1;
    // cin >> awa;
    while (awa--)
    {
        _();
    }
    return 0;
}