题目地址：洛谷：【P2501】[HAOI2006]数字序列 – 洛谷、BZOJ：Problem 1049. — [HAOI2006]数字序列

题目描述

现在我们有一个长度为n的整数序列A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。

输入输出格式

输入格式：
第一行包含一个数n，接下来n个整数按顺序描述每一项的键值。

输出格式：
第一行一个整数表示最少需要改变多少个数。
第二行一个整数，表示在改变的数最少的情况下，每个数改变的绝对值之和的最小值。

输入输出样例

输入样例#1：

4
5 2 3 5

输出样例#1：

1
4

说明

【数据范围】
90%的数据n<=6000。
100%的数据n<=35000。
保证所有数列是随机的。

题解

参考资料：

• 题解 P2501 【[HAOI2006]数字序列】 – Qihoo360 – 洛谷博客
• 【BZOJ】1049: [HAOI2006]数字序列（lis+特殊的技巧） – iwtwiioi – 博客园

如果对于任意的$i, j \ (i < j)$都有$a_j – a_i \geq j – i$，那么这个序列就是单增的了，这是因为保证了元素之间至少有1的差值。既然最少需要改变的个数不好求，那么我们求最多不用改变的个数就好了，我们定义$b_i = a_i – i$，那么最多不用改变的个数就是$b$数组的最长不下降子序列长度了。
后面的问题是如何改变使变化最小，我们观察$b$数组的LIS，设$dp[i]$是以$a_i$结尾的LIS长度，那么如果有$j < i, dp[i] = dp[j] + 1$，那么$[i+1, j-1]$这一段元素就需要修改。我们考虑，这一段元素中，离$j$较近的一段$[j+1, k]$的$b$数组值全修改成$b_j$，而$[k+1, i-1]$全修改成$b_i$是一个最优解（形式化的证明参见参考资料2），那么我们枚举$k$去判断就好了。设$dp2[i]$是前面$i$个元素变成增序列的最小变化，那么可以通过上面枚举$k$的方式转移。
后面这个DP是$O(n^3)$的，由于数据随机，跑不满上限，因此跑的飞快。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 35005;

int n, a[MAXN], dp[MAXN];
LL dp2[MAXN], sum1[MAXN], sum2[MAXN];
int tmp[MAXN], tot;
std::vector<int> vec[MAXN];

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        a[i] = readint() - i;
    }
    a[0] = -1e9; a[++n] = 1e9;
    memset(tmp, 0x3f, sizeof(tmp));
    tmp[0] = -1e9; tmp[1] = a[1]; tot = 1; dp[1] = 1;
    for(int i = 2; i <= n; i++) {
        int p = std::upper_bound(tmp, tmp + tot + 1, a[i]) - tmp;
        tot = std::max(tot, p);
        tmp[p] = a[i];
        dp[i] = p;
    }
    printf("%d\n", n - dp[n]);
    for(int i = 0; i <= n; i++) vec[dp[i]].push_back(i);
    memset(dp2, 0x3f, sizeof(dp2));
    dp2[0] = 0;
    for(int i = 1; i <= n; i++) {
        for(int jj = 0; jj < vec[dp[i] - 1].size(); jj++) {
            int j = vec[dp[i] - 1][jj];
            if(j > i) break;
            if(a[j] > a[i]) continue;
            for(int k = j; k <= i; k++) {
                sum1[k] = abs(a[k] - a[j]); sum2[k] = abs(a[k] - a[i]);
            }
            for(int k = j + 1; k <= i; k++) {
                sum1[k] += sum1[k - 1]; sum2[k] += sum2[k - 1];
            }
            for(int k = j; k < i; k++) {
                dp2[i] = std::min(dp2[i], dp2[j] + sum1[k] - sum1[j] + sum2[i] - sum2[k]);
            }
        }
    }
    printf("%lld", dp2[n]);
    return 0;
}