首页 > 代码库 > 【bzoj1786】[Ahoi2008]Pair 配对 dp
【bzoj1786】[Ahoi2008]Pair 配对 dp
题目描述
输入
输出
样例输入
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]\ (j\le 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\n" , ans); return 0;}
【bzoj1786】[Ahoi2008]Pair 配对 dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。