传送门

深感智商下降，又开始刷$DP$了。

这题关键在于一个很重要的性质：填进去的数字是单调不降的。

考虑我有一个$a$和$b$，$a\le b$。把$b$放到$a$前面，$a,b$会构成逆序对，而且把大的数放前面，与其他数会产生更多的逆序对，显然不优。

这样就随便$DP$了，设$f(i,j)$为前$i$个空位第$i$个空位为$j$的最小逆序对数。

$f(i,j)=\min\limits_{l=1}^jf(i-1,l)+S$

其中$S$表示把$j$放在第$i$个空位与其他非空位产生的逆序对数。

维护前缀最小值+暴力修改前缀和就能$O(nk)$做了。最后答案还要加上序列原有的逆序对。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 10005
#define inf 0x3f3f3f3f

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int f[2][105],a[maxn],sum[105],rev[105];
int main(){
    int n=read(),m=read(),last=0,ans=0;
    for(register int i=1;i<=n;++i){
        a[i]=read();
        if(~a[i])++rev[a[i]];
    }
    for(register int i=1;i<=m;++i)rev[i]+=rev[i-1];
    for(register int i=1;i<=n;++i){
        if(a[i]==-1){
            f[++last&1][0]=inf;
            for(register int j=1;j<=m;++j)
                f[last&1][j]=min(f[last&1][j-1],f[last&1^1][j]+sum[m]-sum[j]+rev[j-1]);
        }
        else {
            for(register int j=a[i];j<=m;++j)--rev[j],++sum[j];
            ans+=rev[a[i]-1];
        }
    }
    printf("%d\n",f[last&1][m]+ans);
}