http://162.105.81.212/JudgeOnline/problem?id=1717
开始想用O(NC)的算法来写，一直WA，后来发现算法是错的，只好用O(NClbM)
#include <iostream> #include <algorithm> #define INF 3000 #define ZERO 6000 using namespace std ; int f[13000] ;// void Negative (int v , int k) { int i ; for (i = 0 ; i + v <= ZERO << 1 ; i ++) f[i] = min (f[i] , f[i + v] + k) ; } void Positive (int v , int k) { int i ; for (i = ZERO << 1 ; i >= v ; i --) f[i] = min (f[i] , f[i - v] + k) ; } int main () { int n , sum , i , up , down , ans , num[13] , k ; bool flag ; for (i = 0 ; i < 13000 ; i ++) f[i] = INF ; scanf ("%d" , &n) ; memset (num , 0 , sizeof (num)) ; for (i = sum = 0 ; i < n ; i ++) { scanf ("%d%d" , &up , &down) ; sum += up - down ;//骨牌上层求和 num[down - up + 6] ++ ;//统计上下层差值的个数 } f[ZERO + sum] = 0 ;//初始化 for (i = 0 ; i < 6 ; i ++)//翻转差值为负 { for (k = 1 ; num[i] >= k ; num[i] -= k , k <<= 1) Negative ((6 - i) * 2 * k , k) ; if (num[i]) Negative ((6 - i) * 2 * num[i] , num[i]) ; } for (i = 7 ; i < 13 ; i ++)//翻转差值为正 { for (k = 1 ; num[i] >= k ; num[i] -= k , k <<= 1) Positive ((i - 6) * 2 * k , k) ; if (num[i]) Positive ((i - 6) * 2 * num[i] , num[i]) ; } for (flag = true , ans = INF , i = 0 ; flag ; i ++) { if (f[ZERO + i] < ans) { flag = false ; ans = f[ZERO + i] ; } if (f[ZERO - i] < ans) { flag = false ; ans = f[ZERO - i] ; } } printf ("%d/n" , ans) ; return 0 ; }
