这个题有意思，刚开始由于不是很理解题意还以为是DP，后来清楚并发现给的Feed的数量很少2^15次方全部弄出来就行了。但关于去最先序列的答案，用位运算^h和&搞定。t&(-t)，取最低位的1还真好使，还有^运算，神奇。
1 #include < iostream > 2 #include < string > 3 #include < algorithm > 4 #include < string .h > 5 #include < vector > 6 #include < math.h > 7 #include < time.h > 8 #include < queue > 9 #include < set > 10 using namespace std; 11 12 const int MAXV = 30 ; 13 const int MAXN = 20 ; 14 15 int n, m, ans, ansState; 16 int all[MAXV]; 17 int sub[MAXN][MAXV]; 18 19 bool check( int x) 20 { 21 int i = 0 ; 22 int t[MAXV]; 23 memset(t, 0 , sizeof (t)); 24 while (x) 25 { 26 if (x & 1 ) 27 { 28 for ( int j = 0 ; j < m; j ++ ) 29 { 30 t[j] += sub[i][j]; 31 } 32 } 33 i ++ ; 34 x >>= 1 ; 35 } 36 for (i = 0 ; i < m; i ++ ) 37 { 38 if (t[i] < all[i]) return false ; 39 } 40 return true ; 41 } 42 43 int getNum( int x) 44 { 45 int res = 0 ; 46 while (x) 47 { 48 if (x & 1 ) res ++ ; 49 x >>= 1 ; 50 } 51 return res; 52 } 53 54 bool checkCMP( int x, int y) 55 { 56 int z = x ^ y; 57 z = z & ( - z); 58 if (z & x) return true ; 59 else return false ; 60 } 61 62 void go() 63 { 64 ans = 100 ; 65 for ( int i = 0 ; i < ( 1 << n); i ++ ) 66 { 67 if (check(i)) 68 { 69 int num = getNum(i); 70 if (num < ans) 71 { 72 ans = num; 73 ansState = i; 74 } 75 else if (num == ans) 76 { 77 if (checkCMP(i, ansState)) 78 { 79 ansState = i; 80 } 81 } 82 } 83 } 84 printf( " %d " , ans); 85 for ( int i = 0 ; i < 20 ; i ++ ) 86 { 87 if (ansState & ( 1 << i)) printf( " %d " , i + 1 ); 88 } 89 printf( " \n " ); 90 } 91 92 int main() 93 { 94 freopen( " holstein.in " , " r " , stdin); 95 freopen( " holstein.out " , " w " , stdout); 96 97 scanf( " %d " , & m); 98 for ( int i = 0 ; i < m; i ++ ) scanf( " %d " , & all[i]); 99 scanf( " %d " , & n); 100 for ( int i = 0 ; i < n; i ++ ) 101 { 102 for ( int j = 0 ; j < m; j ++ ) 103 scanf( " %d " , & sub[i][j]); 104 } 105 go(); 106 }
转载于:https://www.cnblogs.com/litstrong/archive/2010/04/16/1713737.html
相关资源：数据结构—成绩单生成器