思路：

肯定从小往大填合适了

f[i][j]表示第i个数是j的最少逆序对数

f[i][j]=min(f[i-1][k]+cost,f[i][j])

优化一下成O(nk)就好啦~ （不优化也可以过的…）

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N=10005;

int n,k,a[N],f[N][105],g[N][105],vis[105],temp[105];

int main(){

    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++){

        scanf("%d",&a[i]);

        if(~a[i])for(int j=a[i];j;j--)vis[j]++;

        else for(int j=1;j<=k;j++)g[i][j]=vis[j+1];

    }

    memset(vis,0,sizeof(vis));

    for(int i=n;i;i--){

        if(~a[i]){

            for(int j=a[i];j<=k;j++)vis[j]++;

            for(int j=1;j<=k;j++)g[i][j]+=vis[a[i]-1];

        }

        else for(int j=1;j<=k;j++)g[i][j]+=vis[j-1];

    }

    for(int i=1;i<=n;i++){

        memset(vis,0,sizeof(vis));

        vis[0]=0x3f3f3f3f;

        for(int j=1;j<=k;j++){

            f[i][j]=g[i][j]+temp[j];

            vis[j]=min(vis[j-1],f[i][j]);

        }

        for(int j=1;j<=k;j++)temp[j]=vis[j];

    }

    for(int i=2;i<=k;i++)f[n][1]=min(f[n][1],f[n][i]);

    printf("%d\n",f[n][1]);

}