$Link$
有一个长度为 $n$ 的长度序列 $x$，一开始所有元素都是 $0$。你一次可以进行以下两种操作之一：
问最快多少次能把 $x$ 变为给定的序列 $a$。
$1\le n\le2\times10^5,1\le a_i\le 10^9$。
我们考虑把 $a_i$ 拆成 $x_i+y_i$，其中 $x_i$ 是多个单调不降序列 $c_i$ 的和，$y_i$ 是多个单调不升序列 $c_i$ 的和。
显然，答案就是 $\sum_{i=1}^{n}[x_{i-1}>x_i]+[y_{i-1}<y_i]$，这里我们令 $x_0=y_0=x_{n+1}=y_{n+1}=0$。
于是有了一个 $O(na_i)$ 的 $dp$，令 $f_{i,j}$ 表示考虑到第 $i$ 位，第 $i$ 位 $x_i$ 填 $j$ 的答案，直接转移即可。
考虑怎么优化，容易注意到对于任意一位填任意值，答案在这一位上的差不会超过 $2$。而差等于 $2$ 的情况，可以通过调整法把它再变小。
同时，如果填 $p$ 和填 $q$，其中 $p<q$，那么显然填 $p$ 更优。
因此，对于每一位，我们只需要存储取到最小和次小代价时，填的最小的数即可。
时间复杂度 $O(n)$。
$code$
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
51
52
53
54
55
56
57
| #include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
inline int read()
{
int f = 1, x = 0;
char ch;
do{
ch = getchar();
if (ch == '-')
f = -1;
}while(ch < '0' || ch > '9');
do{
x = x * 10 + ch - '0';
ch = getchar();
}while(ch >= '0' && ch <= '9');
return f * x;
}
const int N = 3e5;
int n;
int a[N + 1];
int pos[3], w[2], nxt[3];
int ans;
inline void dp()
{
for (int i = 1; i <= n + 1; i++) {
w[0] = 0;
w[1] = a[i] - a[i - 1];
if (w[0] < w[1])
swap(w[0], w[1]);
nxt[0] = nxt[1] = 1e9;
nxt[2] = 0;
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
nxt[j + k] = min(nxt[j + k], max(0, pos[j] + w[k]));
int d = nxt[0] > a[i];
ans += d;
for (int j = 0; j < 2; j++)
pos[j] = nxt[j + d];
}
return;
}
int main()
{
n = read();
for (int i = 1; i <= n; i++)
a[i] = read();
dp();
printf("%d\n", ans);
return 0;
}
|