0%

[CF1437E] Make It Increasing

题目

题目链接

题目大意:给出长度为 $n$ 的序列,每次可以修改任意一个下标不在 $b$ 中的元素,问最少的操作次数使得原序列单调递增,无解输出 $-1$。$1 \le n \le 5 \cdot 10^5, 1 \le a_i \le 10^9$。

思路

难得有一次 cf 除了 div 3 能打到 E…

先考虑没有限制的情况,这是一个很经典的 DP 问题,设 $c_i = a_i - i$ 之后求 $c$ 的最长不下降子序列即可。

现在有对位置的限制,首先考虑无解的情况,这个很显然,没什么可说的。

如果第 $i$ 个元素不能修改,意味着第 $i$ 个元素必须在我们的最长不下降子序列中,不然就不可能符合单调递增的条件。

然后只需要对 $O(n \log n)$ 求最长不下降子序列的算法进行一些改变即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

int a[500010], b[500010], f[500010];
int n, k, len, lst;
bool can[500010];
bool flag = true;

int main() {
read(n), read(k);
for (int i = 1; i <= n; ++i) read(a[i]);
for (int i = 1; i <= k; ++i) read(b[i]), can[b[i]] = true;
for (int i = 2; i <= k; ++i) {
if (a[b[i]] < a[b[i - 1]] || a[b[i]] - a[b[i - 1]] < b[i] - b[i - 1]) {
flag = false;
break;
}
}
if (!flag) {
puts("-1");
return 0;
}
for (int i = 1; i <= n; ++i) a[i] -= i;
for (int i = 1; i <= n; ++i) {
if (a[i] >= f[len]) {
f[++len] = a[i];
if (can[i]) lst = len;
} else {
int p = std::upper_bound(f + 1, f + len + 1, a[i]) - f;
if (p <= lst) continue;
f[p] = a[i];
if (can[i]) lst = p, len = p;
}
}
printf("%d\n", n - len);
return 0;
}