题解：P11727 [JOIG 2025] 神経衰弱 2 / Pair Matching 2

ELECTRODE_kaf · 2025-02-15 19:25:00 · 题解

首先可以发现选择的牌必须产生贡献（否则只会占用空间不如不选）。其次产生贡献的一对牌之间最多再选择一张牌（否则前一张牌会被扔掉），所以最佳选择方案一定形如 AABB 或 ABAB。

预处理每个 A_i 上次出现的位置 pre_i（未出现过则为 0）。

考虑 DP。设 dp_i 表示消除 A_i 的最大价值。此时有两种转移方式：①从 A_{pre_i} 之前转移；②从一个 pre_j<pre_i 转移。称它们为第 1/2 种方式。设 dp_{i,0/1} 表示以第 1/2 种方式消除 A_i 的最大价值。第一种方式从最大值转移。第二种方式则需要将 dp_{i,0} 记录在 pre_i 的位置上，然后从 j\le pre_i 的位置转移。树状数组维护。

const ll N = 8e5 + 10;
ll n, a[N], v[N], pre[N], dp[N][2], temp[N], ans[N], bt[N];

ll lowbit(ll x) {
    return x & -x;
}

void add(ll p, ll x) {
    while (p <= n * 2) {
        update(bt[p], x, max);
        p += lowbit(p);
    }
}

ll query(ll p) {
    ll ret = 0;

    while (p) {
        update(ret, bt[p], max);
        p -= lowbit(p);
    }

    return ret;
}

ll max3(ll a, ll b, ll c) {
    return max(max(a, b), c);
}

int main() {
    cin >> n;
//  memset(temp,0,sizeof(temp));
//  memset(dp,0,sizeof(dp));
//  memset(pre,0,sizeof(pre));

    rep(i, 1, n * 2)
        cin >> a[i];

    rep(i, 1, n * 2) {
        if (temp[a[i]])
            pre[i] = temp[a[i]];
        else
            temp[a[i]] = i;
    }

    rep(i, 1, n) cin >> v[i];

    rep(i, 1, n * 2) {
        if (pre[i] == 0)
            ans[i] = ans[i - 1];
        else {
            dp[i][1] = query(pre[i]) + v[a[i]];
            dp[i][0] = ans[pre[i] - 1] + v[a[i]];
            add(pre[i], dp[i][0]);
            update(ans[i], max3(dp[i][0], dp[i][1], ans[i - 1]), max);
        }
    }

    cout << ans[n * 2];
}