[文章目录]
Description
小可可和小卡卡想到Y岛上旅游，但是他们不知道Y岛有多远。好在，他们找到一本古老的书，上面是这样说的： 下面是N个正整数，每个都在1~K之间。如果有两个数A和B，A在B左边且A大于B，我们就称这两个数为一个“逆序对”。你数一数下面的数字里有多少个逆序对，你就知道Y岛离这里的距离是多少千米了。 比如说，4 2 1 3 3里面包含了5个逆序对：(4, 2), (4, 1), (4, 3), (4, 3), (2, 1)。 可惜的是，由于年代久远，这些数字里有一部分已经模糊不清了，为了方便记录，小可可用“-1”表示它们。比如说，4 2 -1 -1 3 可能原来是4 2 1 3 3，也可能是4 2 4 4 3，也可能是别的样子。 小可可希望知道，根据他们看清楚的这部分数字，能不能推断出这些数字里最少能有多少个逆序对。n<=10000 k<=100
结论：-1的位置的序列一定是不降的，并且显然-1中填的数一定是出现过的。
那么我们就可以DP了吧，维护一个前缀最小值，时间复杂度O(n*k)。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,a[10100],sfro[10100][110],saft[10100][110],dp[10100][110],ans;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",a+i);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
sfro[i][j]=sfro[i-1][j];
if(a[i]!=-1) sfro[i][a[i]]++;
}
for(int i=n;i;--i)
{
for(int j=1;j<=m;++j)
saft[i][j]=saft[i+1][j];
if(a[i]!=-1) saft[i][a[i]]++;
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
saft[i][j]+=saft[i][j-1];
for(int j=m;j;--j)
sfro[i][j]+=sfro[i][j+1];
if(a[i]!=-1) ans+=saft[i][a[i]-1];
}
memset(dp,0x3f,sizeof dp); memset(dp[0],0,sizeof dp[0]);
int now=0;
for(int i=1;i<=n;++i) if(a[i]==-1)
{
now++;
for(int j=1;j<=m;++j)
dp[now][j]=min(dp[now][j-1],dp[now-1][j]+saft[i][j-1]+sfro[i][j+1]);
}
int fna=inf;
for(int i=1;i<=m;++i) fna=min(fna,dp[now][i]);
printf("%d\n",ans+fna);
return 0;
}