题目描述
给定一个由 $[1,k]$ 之间的数字组成的长度为 $n$ 序列，其中有一些位置上的数不可见，标记为 $-1$，求这个序列的最少逆序对数。
$n\le 10000$，$k\le 100$。
算法分析
首先需要发现一个结论：要使逆序对数最少，从前到后依次填写的不可见的数字一定单调不下降。
一个感性的理解是，如果填写的数字不满足单调不下降，那么其本身就会产生逆序对。但这样似乎不太严谨，考虑如何证明。
设两个待填写的位置 $x,y$ 上的数 $A,B$，有 $x\lt y,A\le B$，$[1,x-1]$ 中比 $A$ 大的数的个数为 $a$，比 $B$ 大的数的个数为 $b$，$[x+1,y]$ 中比 $A$ 大的数的个数为 $c$，比 $B$ 大的数的个数为 $d$。
则当 $A$ 在 $x$ 而 $B$ 在 $y$ 时，两者对答案的贡献为 $a+b+d$；当 $B$ 在 $x$ 而 $A$ 在 $y$ 时，两者对答案的贡献为 $b+a+c+1$。由于 $A\le B$，因此 $c\ge d$，则 $a+b+d\lt b+a+c+1$。所以将值更小的数放在前面得到的逆序对数更少。
有了这个结论之后就可以 DP 了，设 $f[i][j]$ 表示前 $i$ 个数字中，不可见的数已经填到了数字 $j$ 的最小逆序对数，暴力 DP 然后用前缀和优化一下就好，时间复杂度为 $O(nk)$。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include <cstdio>
#include <cstring>
#include <algorithm>
#define N 10005
int a[N],f[N][105],front[105],back[105];
int main() {
int n,k;scanf("%d%d",&n,&k);
for(register int i=1;i<=n;++i) {scanf("%d",a+i);if(~a[i]) ++back[a[i]];}
for(register int i=2;i<=k;++i) back[i]+=back[i-1];
memset(f,0x3f,sizeof(f));f[0][1]=0;
for(register int i=1;i<=n;++i) {
if(~a[i]) {
for(register int j=1;j<=k;++j) f[i][j]=f[i-1][j]+back[a[i]-1];
for(register int j=a[i];j<=k;++j) ++front[j],--back[j];
}
else {
for(register int j=1;j<=k;++j) f[i][j]=f[i-1][j];
for(register int j=2;j<=k;++j) f[i][j]=std::min(f[i][j],f[i][j-1]);
for(register int j=1;j<=k;++j) f[i][j]+=back[j-1]+front[k]-front[j];
}
}
int ans=0x3f3f3f3f;
for(register int i=1;i<=k;++i) ans=std::min(ans,f[n][i]);
printf("%d\n",ans);
return 0;
}
|