题目大意：给一个n个数的序列，每个数都是[1,k]内的整数或-1，-1代表这个格子是空的，有p个格子是-1。

现在要你在空的格子填上[1,k]的数，使得整个序列逆序对数量最少。输出最小值。

$ n \leq 100000, k \leq 100, p \leq 10000$

入门：$O(nk^2)$

进阶：$O(nk)$

$TL:1s, ML:64Mb$

P.S 开不下$n \times k$的数组。

首先我们发现-1的地方有些奇怪的性质。比如空格填的数单调不降。（似乎可以证明）

证明：http://www.cnblogs.com/htfy/archive/2012/12/11/2813497.html

所以我们设f[i,j]表示 第i个空格，填j的最小逆序对数量。

那么f[i,j] = min{f[i-1, k]} + delta  (1<=k<=j)

delta表示填了这个数之后，在他之前和之后增加的逆序对个数。

这个可以通过前缀和（迷？）来搞定

# include <stdio.h>
# include <algorithm>
using namespace std;

const int M=100010, MM=10010, Ms=110;
int n, k, a[M];
int bucket[Ms], nb[Ms];
int ans;
int f[MM][Ms];
int s[Ms], ss[Ms];
//f[i,j] 第i个-1 填j的最小代价 

int main() {
	scanf("%d%d", &n, &k);
	for (int i=1; i<=n; ++i) {
		scanf("%d", &a[i]);
		if(a[i] != -1) {
			for (int j=k; j>a[i]; --j) 
				ans = ans + bucket[j];
			bucket[a[i]] ++;
		}
	}
	int nn = 0;
	for (int i=1; i<=n; ++i) {
		if(a[i] == -1) {
			nn++;
			for (int j=1; j<=k; ++j) s[j] = s[j-1] + bucket[j] - nb[j];
			for (int j=k; j>=1; --j) {
				f[nn][j] = f[nn-1][j] + ss[j+1] + s[j-1];
				ss[j] = ss[j+1] + nb[j];
			}
			for (int j=2; j<=k; ++j) f[nn][j] = min(f[nn][j], f[nn][j-1]);
		} else nb[a[i]] ++;
	}
	printf("%d\n", f[nn][k] + ans);
	return 0;
}