#BZOJ1786

BZOJ1786 [Ahoi2008]Pair 配对 动态规划 逆序对

  给出长度为n的数列,只会出现1~k这些正整数。现在有些数写成了-1,这些-1可以变成任何数。  求把这些-1变成1~k中的正整数之后,最少的逆序对个数为多少。   我们可以判断,这些-1中写的数字一定是单调不降的。  为什么?我们把答案序列的所有-1位抽出来,如果答案序列中有一组是逆序的,那么交换他们,一...