题目描述

Description

Input

Output

Sample Input

5 4 
4 2 -1 -1 3 

Sample Output

4

题目分析

考虑 -1填入的数一定单调不降
证明一下：
考虑-1与-1之间 一定单调不降更优
考虑-1与数之间 如果把一个数放在这里会和前面的数会产生逆序对 那么放哪里都会产生逆序对 如果把一个数放在这里会和后面的数会产生逆序对 那还不如把它尽可能的放在后面
然后就可以DP了
f[i][j]表示第i个位置放j的最少逆序对
先预处理出前缀比一个数大 后缀比一个数小 的个数
然后再用一个前缀min优化DP就可以了
注意 当一个位置不是-1 只考虑它与它前面/后面产生的逆序对 否则会算重

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,k;
int a[10010];
int sum[10010][110],sum2[10100][110];
int f[10100][110];
int g[2][110];
int main()
{   
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=k;j++) sum[i][j]=sum[i-1][j]+(a[i]==j);
    for(int i=n;i>=1;i--) 
        for(int j=1;j<=k;j++) sum2[i][j]=sum2[i+1][j]+(a[i]==j);
    for(int i=1;i<=n;i++)
        for(int j=k;j>=1;j--) sum[i][j]+=sum[i][j+1];
    for(int i=n;i>=1;i--)
        for(int j=1;j<=k;j++) sum2[i][j]+=sum2[i][j-1];
    memset(f,0x3f,sizeof f);
    f[0][1]=0;
    for(int i=1;i<=n;i++)
    {
        g[2][0]=0x3f3f3f3f;
        if(a[i]==-1)
        {
            for(int j=1;j<=k;j++)
            {
                f[i][j]=g[1][j]+sum[i-1][j+1]+sum2[i+1][j-1];
                g[2][j]=min(g[2][j-1],f[i][j]);
            }
        }
        else
        {
            for(int j=1;j<=k;j++) f[i][j]=f[i-1][j]+sum[i-1][a[i]+1];
            for(int j=1;j<=k;j++) g[2][j]=min(g[2][j-1],f[i][j]);  
        }
        for(int j=1;j<=k;j++) g[1][j]=g[2][j],g[2][j]=0x3f3f3f3f;
    }    
    int ans=0x3f3f3f3f;
    for(int i=1;i<=k;i++) ans=min(ans,f[n][i]);
    printf("%d",ans);
    return 0;
}