题目描述
输入
输出
样例输入
5 4
4 2 -1 -1 3
样例输出
4
题解
dp
首先有个结论：填入的数一定是单调不降的。
证明：假设$i<j$，$a_i>a_j$，那么交换$a_i$和$a_j$，对逆序对总数产生的影响只有$[i+1,j-1]$这段区间及$i$和$j$。对于中间的部分，交换后$i$位置上的数变小，使得与中间位置的数产生的逆序对数不增；交换后$j$位置上的数变大，同样使得与中间位置的数产生的逆序对数不增；交换了$a_i$和$a_j$，使得总逆序对数-1。所以一定不如交换后更优。
那么产生的逆序对只有两种情况：原来确定的数之间、原来确定的数与填入的数之间。
于是我们就可以dp：设$f[i][j]$表示枚举到位置$i$，上一个填入的数是$j$的最小逆序对数。那么如果$i$位置的数是确定的，只需要计算答案，并把$f[i-1]$的状态复制过来。
如果$i$位置的数不是确定的，那么枚举这个数为$t$，则$f[i][t]=min(f[i-1][j])+ans[i][t] (jle t)$，其中$ans[i][t]$为i位置填入t产生的逆序对数。
那么对于前面的部分维护一个前缀最小值即可，后面的部分由于k很小，所以使用二维前缀和与后缀和维护，$O(1)$查询。
最后的答案即为$f[n][t]$，总的时间复杂度为$O(nk)$
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[10010] , f[10010][110] , s1[10010][110] , s2[10010][110];
int main()
{
int n , k , i , j , ans = 1 << 30 , tmp;
scanf("%d%d" , &n , &k);
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]);
for(i = 1 ; i <= n ; i ++ )
for(j = k ; j >= 1 ; j -- )
s1[i][j] = s1[i - 1][j] + s1[i][j + 1] - s1[i - 1][j + 1] + (a[i] == j);
for(i = n ; i >= 1 ; i -- )
for(j = 1 ; j <= k ; j ++ )
s2[i][j] = s2[i + 1][j] + s2[i][j - 1] - s2[i + 1][j - 1] + (a[i] == j);
memset(f , 0x3f , sizeof(f)) , f[0][1] = 0;
for(i = 1 ; i <= n ; i ++ )
{
if(~a[i])
for(j = 1 ; j <= k ; j ++ )
f[i][j] = f[i - 1][j] + s1[i - 1][a[i] + 1];
else
for(j = 1 , tmp = 1 << 30 ; j <= k ; j ++ )
tmp = min(tmp , f[i - 1][j]) , f[i][j] = tmp + s1[i - 1][j + 1] + s2[i + 1][j - 1];
}
for(i = 1 ; i <= k ; i ++ ) ans = min(ans , f[n][i]);
printf("%d
" , ans);
return 0;
}