P2501-[HAOI2006]数字序列
题目:
题目描述:
现在我们有一个长度为 $n$ 的整数序列 $a$。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。
输入格式:
第一行是一个整数，表示序列长度 $n$。
第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 项 $a_i$。
输出格式:
第一行输出一个整数，表示最少需要改变多少个数。
第二行输出一个整数，表示在改变的数最少的情况下，每个数改变的绝对值之和的最小值。
样例:
样例输入 1:
样例输出 1:
思路:
实现:
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
58
59
60
61
62
63
| #include "ybwhead/ios.h"
// #define rep(i, m, n) for (int i = m; i <= n; ++i)
// #define dop(i, m, n) for (int i = m; i >= n; --i)
// #define each(i, m, v) for (int i = head[m], v = e[i].to; i; i = e[i].next, v = e[i].to)
// #define lowbit(x) (x & (-x))
// #define ll long long
const long long INF = 1073741824;
// #define re register
// using namespace std;
const int maxn = 35010;
int n, a[maxn], c[maxn], dp[maxn], len, tmp, num, head[maxn];
long long f[maxn], sum1[maxn], sum2[maxn];
struct Edge
{
int to, nxt;
} e[maxn];
void Add(int from, int to)
{
e[++num].to = to;
e[num].nxt = head[from];
head[from] = num;
} //邻接表
int main()
{
yin >> n;
for (int i = 1; i <= n; i++)
yin >> a[i], a[i] = a[i] - i;
for (int i = 1; i <= n; i++)
c[i] = INF;
c[0] = -INF;
dp[1] = 1;
len = 1;
a[++n] = INF;
c[1] = a[1];
a[0] = -INF;
for (int i = 2; i <= n; i++)
{
tmp = upper_bound(c, c + 1 + len, a[i]) - c;
len = max(len, tmp);
dp[i] = tmp;
c[tmp] = min(c[tmp], a[i]);
}
yout << n - dp[n] << endl;
for (int i = n; i >= 0; i--)
Add(dp[i], i), f[i] = INF;
f[0] = 0;
for (int i = 1; i <= n; i++)
for (int j = head[dp[i] - 1], to = e[j].to; j; j = e[j].nxt, to = e[j].to)
{
if (to > i)
break;
if (a[to] > a[i])
continue;
for (int k = to; k <= i; k++)
sum1[k] = abs(a[k] - a[to]), sum2[k] = abs(a[k] - a[i]);
for (int k = to + 1; k <= i; k++)
sum1[k] += sum1[k - 1], sum2[k] += sum2[k - 1];
for (int k = to; k <= i - 1; k++)
f[i] = min(f[i], f[to] + sum1[k] - sum1[to] + sum2[i] - sum2[k]);
}
yout << f[n] << endl;
return 0;
}
|