Solution「『CF2161D Locked Out』题解」

退役之前整理自己的遗物，把最后一篇想写的 tj 写完。

其实也是第一次写 hint 驱动式的 tj。

题意

原题

一个序列 $b$ 是好的，当且仅当不存在 $1\leq i<j\leq n$ ，使 $b_j-b_i=1$ 。
给定一个序列 $a$ ，求需要删除多少个数才能使得它变成好的。
多组数据， $1\leq n\leq3\times10^5$ ， $1\leq a_i\leq n$ 。

提示 1

考虑如何刻画「好的」序列。

提示 1.1

如果

l\sim r

的每一个数都存在于序列

b

中，那它们应该排列成什么形状？

提示 1.2

如果

x

不存在于序列

b

中，那小于

x

的数和大于

x

的数之间有影响吗？

答案

如果

l\sim r

的每一个数都存在于序列

b

中，那它们必须排成

r,r,\cdots,r,r-1,r-1,\cdots,r-1,\cdots,l,l,\cdots,l

的形状，即单调不增。

这样子可以形成多个在值域上连续的段。「好的」序列即将这些段之间交错拼接。

提示 2

考虑如何贪心地维护这样的序列。

提示 2.1

考虑从小到大枚举序列里的一个数值

x

，讨论它要加进已经是「好的」且值均

<x

的子序列中的情形。

提示 2.2

添加方案只有以下两种：

将 $x$ 添加到 $x-1$ 的头部（不添加 $x$ 也属于这一种情形）；
撤回添加 $x-1$ 的操作，以保证 $x$ 完全添加到序列中。

题解

阅读提示。

枚举序列

a

，把每个数的出现位置罗列出来。

在提示 2.1 的情形下，考虑提示 2.2 的两种情况。

第一种情况：考虑类似归并排序地合并值为 $x$ 的子序列与已经加入的、值为 $x-1$ 的子序列，并且在合并的过程中计算答案。
第二种情况：直接继承 $x-2$ 时计算的答案。

从中选择更优的即可。

我们讨论了两种情况，却说明从中选出更优的。但是，如果两个方案同样优秀怎么办？

这个和一般的 dp 不一样：这一步的选择直接影响到了加入的值为

x

的元素，进而影响

x+1

时答案的计算。

这时我的选择是：应当选用第二种情况。原因很简单：若对于

x+1

，第一种情况的答案为

t

，那么对于第二种情况，删除值为

x

的元素时可以选择与第一种情况时删的一样，这样答案也可以到达

t

。

不过实测结果是，选用第一种情况也可以。不知道为什么。

代码

CPP

1234567891011121314151617181920212223242526272829303132333435363738394041#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
int T, n, a[N], dp[N], rt[N];
vector <int> pos[N];
int main () {
	scanf ("%d", &T);
	while (T --> 0) {
		scanf ("%d", &n);
		fill (pos + 1, pos + n + 1, vector <int> ());
		for (int i = 1; i <= n; i++) {
			scanf ("%d", &a[i]);
			pos[a[i]].push_back (i);
		}
		rt[1] = pos[1].size () - 1;
		for (int i = 2; i <= n; i++) {
			int t = -1, s = pos[i].size ();
			for (int j = 0, k = 0; j <= rt[i - 1] || k < (int) pos[i].size (); ) {
				if (k == (int) pos[i].size () || (j <= rt[i - 1] && pos[i - 1][j] < pos[i][k])) {
					j++;
				} else {
					int u = j + pos[i].size () - k - 1;
					if (u < s) {
						t = k;
						s = u;
					}
					k++;
				}
			}
			if (dp[i - 2] + (int) pos[i - 1].size () >= dp[i - 1] + s) {
				dp[i] = dp[i - 1] + s;
				rt[i] = t;
			} else {
				dp[i] = dp[i - 2] + pos[i - 1].size ();
				rt[i] = pos[i].size () - 1;
			}
		}
		printf ("%d\n", dp[n]);
	}
	return 0;
}

Solution「『CF2161D Locked Out』题解」

文章操作

相关推荐

评论

Solution「『CF2161D Locked Out』题解」