题目地址：洛谷：【P4280】[AHOI2008]逆序对 – 洛谷、BZOJ：Problem 1831. — [AHOI2008]逆序对

题目描述

暑假到了，小可可和伙伴们来到海边度假，距离海滩不远的地方有个小岛，叫做欢乐岛，整个岛是一个大游乐园，里面有很多很好玩的益智游戏。碰巧岛上正在举行“解谜题赢取免费门票”的活动，只要猜出来迷题，那么小可可和他的朋友就能在欢乐岛上免费游玩两天。
迷题是这样的：给出一串全部是正整数的数字，这些正整数都在一个范围内选取，谁能最快求出这串数字中“逆序对”的个数，那么大奖就是他的啦！
当然、主办方不可能就这么简单的让迷题被解开，数字串都是被处理过的，一部分数字被故意隐藏起来，这些数字均用-1来代替，想要获得大奖就必须求出被处理的数字串中最少能有多少个逆序对。小可可很想获得免费游玩游乐园的机会，你能帮助他吗？
注：“逆序对”就是如果有两个数A和B，A在B左边且A大于B，我们就称这两个数为一个“逆序对”，例如：4 2 1 3 3里面包含了5个逆序对：(4, 2)、(4, 1)、(4, 3)、(4, 3)、(2, 1)。
假设这串数字由5个正整数组成，其中任一数字N均在1～4之间，数字串中一部分数字被“-1”替代后，如：4 2 -1 -1 3 ，那么这串数字，可能是4 2 1 3 3，也可能是4 2 4 4 3，也可能是别的样子。你要做的就是根据已知的数字，推断出这串数字里最少能有多少个逆序对。

题意简述

一个序列中有一些空位，求所有填空方案中序列逆序对数最小为多少。

输入输出格式

输入格式：
第一行两个正整数N和K；
第二行N个整数，每个都是-1或是一个在1~K之间的数（N<=10000，K<=100）。

输出格式：
一个正整数，即这些数字里最少的逆序对个数。

输入输出样例

输入样例#1：

5 4
4 2 -1 -1 3

输出样例#1：

4

说明

100%的数据中，N<=10000，K<=100。
60%的数据中，N<=100。
40%的数据中，-1出现不超过两次。

题解

有一个贪心的结论是，在空位上填上单调不降的数字会更好。我们可以假设i < j且a[i] < a[j]，如果交换a[i]和a[j]，对a[1]~a[i-1]以及a[j+1]~a[n]产生的逆序对无影响，对于a[i+1]~a[j-1]之间且不在(a[i], a[j])区间内的数字也无影响，只会影响在该区间内的数字，可以发现，对于这些数字，逆序对数显然增加了。因此我们证明了，单调不降答案不会变差。
于是我们发现填单调不降序列无后效性，可以开始愉快地DP了。设计状态dp[i][j]表示填到第i个空且该位置填j的逆序对数，显然有以下转移
dp[i][j] = \min_{1 \leq k \leq j} \{ dp[i-1][j] \} + 该位置填j的逆序对数
中间用到的min，我们可以在转移的时候顺便处理出来，因此整个DP可以实现O(nk)的复杂度。
最后的答案是 \min_{1 \leq i \leq k} \{ dp[n'][i] \} + 原有逆序对数 。

代码

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

#include <algorithm>
#include <queue>

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();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 10005;

int n, k, a[MAXN], pre[MAXN][105], nxt[MAXN][105], mn[MAXN][105], dp[MAXN][105], pos[MAXN], tot;

int main() {
    n = readint(); k = readint();
    for(int i = 1; i <= n; i++) {
        a[i] = readint();
        if(a[i] == -1) pos[++tot] = i;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k; j++) {
            pre[i][j] = pre[i - 1][j] + (j < a[i]);
        }
    }
    for(int i = n; i; i--) {
        for(int j = 1; j <= k; j++) {
            nxt[i][j] = nxt[i + 1][j] + (j > a[i] && a[i] != -1);
        }
    }
    for(int i = 1; i <= tot; i++) {
        mn[i][1] = dp[i][1] = mn[i - 1][1] + pre[pos[i]][1] + nxt[pos[i]][1];
        for(int j = 2; j <= k; j++) {
            dp[i][j] = mn[i - 1][j] + pre[pos[i]][j] + nxt[pos[i]][j];
            mn[i][j] = std::min(mn[i][j - 1], dp[i][j]);
        }
    }
    int ans = 1e9;
    for(int i = 1; i <= k; i++) {
        ans = std::min(ans, dp[tot][i]);
    }
    for(int i = 1; i <= n; i++) {
        if(a[i] != -1) ans += pre[i][a[i]];
    }
    printf("%d", ans);
    return 0;
}