[HAOI 2006] 数字序列

题目大意

给定一个长为 nn 的序列 {ai}\{a_i\} ,改变一些数使其成为严格单调递增序列,求需改变数的最少值,以及在这种情况下,每个数改变的绝对值之和的最小值。

1n35,0001 \leqslant n \leqslant 35,000

题目链接

【HAOI 2006】数字序列 - Luogu 2501

题解

DP。

aiia_i - i 得到一个新序列 {bi}\{b_i\} ,原题变为使其成为不下降序列。

第一问,记 f(i)f(i) 表示 [1,i][1, i] 的最长不下降子序列

f(i)=max(f(j)+1,  bjbi)0<j<if(i) = max(f(j) + 1, \; b_j \leqslant b_i) \quad 0 < j < i

答案为 nf(n)n - f(n)

第二问,在序列两头分别补上序列中的最小值、最大值,记 g(i)g(i) 表示区间 [1,i][1, i]bib_i 不变时的答案

g(i)=max(g(j)+cost(i,j),  f(i)=f(j)+1)0j<ig(i) = max(g(j) + cost(i, j), \; f(i) = f(j) + 1) \quad 0 \leqslant j < i

其中 cost(i,j)cost(i, j) 表示区间 [i,j][i, j]bib_ibjb_j 不变时的答案。由于有 f(i)=f(j)+1f(i) = f(j) + 1 ,则不存在 k(i,j)k \in (i, j) 使得 bjbkbib_j \leqslant b_k \leqslant b_i 。对于该区间的最优解,一定是把前一部分改为 bjb_j ,后一部分改为 bib_i ,枚举中间的分割线更新答案。

代码

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
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <algorithm>
const int MAXN = 35005;
int main() {
int n;
scanf("%d", &n);
static int a[MAXN];
a[0] = INT_MAX;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
a[i] -= i;
a[0] = std::min(a[0], a[i]);
a[n + 1] = std::max(a[n + 1], a[i]);
}
static int f[MAXN];
for (int i = 1; i <= n; i++) for (int j = 0; j < i; j++) {
if (a[j] <= a[i] && f[j] + 1 > f[i]) f[i] = f[j] + 1;
}
printf("%d\n", n - f[n]);
static int g[MAXN];
for (int i = 1; i <= n + 1; i++) {
g[i] = INT_MAX;
for (int j = 0; j < i; j++) {
if (a[j] <= a[i] && f[j] + 1 == f[i]) {
int w = 0;
for (int k = j + 1; k < i; k++) w += abs(a[k] - a[j]);
g[i] = std::min(g[i], g[j] + w);
for (int k = i - 1; k > j; k--) {
w -= abs(a[k] - a[j]);
w += abs(a[k] - a[i]);
g[i] = std::min(g[i], g[j] + w);
}
}
}
}
printf("%d\n", g[n + 1]);
return 0;
}