专栏文章

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

EELECTRODE_kaf
P11727题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq8xras
此快照首次捕获于
2025/12/04 00:53
3 个月前
此快照最后确认于
2025/12/04 00:53
3 个月前
查看原文
首先可以发现选择的牌必须产生贡献（否则只会占用空间不如不选）。其次产生贡献的一对牌之间最多再选择一张牌（否则前一张牌会被扔掉），所以最佳选择方案一定形如 AABB 或 ABAB。
预处理每个 AiA_i 上次出现的位置 preipre_i（未出现过则为 00）。
考虑 DP。设 dpidp_i 表示消除 AiA_i 的最大价值。此时有两种转移方式：①从 ApreiA_{pre_i} 之前转移；②从一个 prej<preipre_j<pre_i 转移。称它们为第 1/21/2 种方式。设 dpi,0/1dp_{i,0/1} 表示以第 1/21/2 种方式消除 AiA_i 的最大价值。第一种方式从最大值转移。第二种方式则需要将 dpi,0dp_{i,0} 记录在 preipre_i 的位置上，然后从 j≤preij\le pre_i 的位置转移。树状数组维护。
CPP
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];
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...