题目描述

甩个链接就走

题解

先预处理出每个位置上分别填上 1~k 的数的逆序对的数量的前缀和与后缀和 (不用管原来有值的,统计时不计入答案就行了)

(有点绕,看代码应该能懂)

然后枚举每个 -1 的位置填的数

设 dp[i][j] 表示填到第 i 个 -1 填且第 i 个数为 j 的当前最小逆序对数量

sum1[i][j] 表示第 i 个数 (不是第 i 个 -1 !!!)填 j 时的逆序对前缀和

sum2[i][j] 表示第 i 个数填 j 时的逆序对后缀和

num[i] 表示第 i 个 -1 出现的位置

则有 :

 dp[i][i] = min (dp[i][j-1], dp[i-1][j] + sum1[ num[i]][j] + sum2[num[i]][j]);

然后统计答案的时候要记得加上每个原本有值的位置的前缀逆序对

即: if ( a[i] != -1 ) ans = sum[i][a[i]] ;

代码 (就不写注释了,前面都讲过了)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
#define in inline
#define get getchar()
in int read()
{
    int t=0,x=1; char ch=get;
    while ((ch<'0' || ch>'9') && ch!='-') ch=get;
    if(ch=='-') ch=get,x=-1;
    while (ch<='9' && ch>='0') t=t*10+ch-'0',ch=get;
    return t*x;
}
const int _=10011;
int sum1[_][101],sum2[_][101],dp[_][201],a[_],n,k,num[_],tot;
int main()
{
    n=read(),k=read();
    for(re int i=1;i<=n;i++)
    {
        a[i]=read();
        if(a[i]==-1)
            num[++tot]=i;
    }
    for(re int i=1;i<=n;i++)
        for (re int j=1;j<=k;j++)
        {
            sum1[i][j]+=sum1[i-1][j];
            if(a[i]>j)sum1[i][j]++;
        }
    for(re int i=n;i>=1;i--)
    {
        for(re int j=1;j<=k;j++)
        {
            sum2[i][j]+=sum2[i+1][j];
            if(a[i]<j&&a[i]!=-1) sum2[i][j]++;
        }
    }
    for(re int i=1;i<=tot;i++)
    {
        dp[i][0]=0x3f3f3f3f;
        for(re int j=1;j<=k;j++) {
            int minn = 0x3f3f3f3f;
            dp[i][j]=min(dp[i][j-1],dp[i-1][j]+sum1[num[i]][j]+sum2[num[i]][j]);
        }
    }
    int ans=dp[tot][k];
    for(re int i=1;i<=n;i++)
    {
        if(a[i]==-1)continue;
        ans+=sum1[i][a[i]];
    }
    cout<<ans<<endl;
    return 0;
}