这道题蛮有意思的，大意是有三个水桶ABC，只有C水桶放满水，从一个水桶倒到另一个水桶，要么一个桶空，要么一个桶满为止，问说当A桶空时，C桶可能出现的所有的可能状态。
比较容易想到的是讲(a,b,c)表示为状态，然后暴力搜索出所有的可能性，因为一共就3个桶，操作也不复杂，对使用过的状态进行标记，这样可以在O(N3)完成，因为USACO的数据很小,<=20,所以就直接AC掉了，看了ANALYSIS之后知道，其实状态用N2就可以搞定，这样O(N2)就可以完成了。
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 using namespace std; 10 11 const int MAX = 1005 ; 12 13 struct WATER 14 { 15 int a, c; 16 WATER( int aa, int cc) : a(aa), c(cc) {} 17 WATER(){} 18 }; 19 20 int A, B, C; 21 queue < WATER > water; 22 vector < int > ans; 23 bool use[MAX][MAX]; 24 // 存a和c的水量就行b = C - a - c 25 // 状态只有O(n*n) 26 27 void pour( int & x, int & y, int X, int Y) 28 { 29 if (x <= Y - y) 30 { 31 y += x; 32 x = 0 ; 33 } 34 else 35 { 36 x -= (Y - y); 37 y = Y; 38 } 39 } 40 41 void judge( int a, int b, int c) 42 { 43 if (use[a][c] == false ) 44 { 45 use[a][c] = true ; 46 water.push(WATER(a, c)); 47 } 48 } 49 50 void check( int a, int b, int c) 51 { 52 int aa = a; 53 int bb = b; 54 int cc = c; 55 56 pour(a, b, A, B); 57 judge(a, b, c); 58 a = aa, b = bb, c = cc; 59 60 pour(a, c, A, C); 61 judge(a, b, c); 62 a = aa, b = bb, c = cc; 63 64 pour(b, a, B, A); 65 judge(a, b, c); 66 a = aa, b = bb, c = cc; 67 68 pour(b, c, B, C); 69 judge(a, b, c); 70 a = aa, b = bb, c = cc; 71 72 pour(c, a, C, A); 73 judge(a, b, c); 74 a = aa, b = bb, c = cc; 75 76 pour(c, b, C, B); 77 judge(a, b, c); 78 a = aa, b = bb, c = cc; 79 } 80 81 void go() 82 { 83 while ( ! water.empty()) 84 { 85 WATER w = water.front(); 86 if (w.a == 0 ) ans.push_back(w.c); 87 water.pop(); 88 check(w.a, C - w.a - w.c, w.c); 89 } 90 91 sort(ans.begin(), ans.end()); 92 for ( int i = 0 ; i < ans.size(); i ++ ) 93 { 94 if (i) printf( " %d " , ans[i]); 95 else printf( " %d " , ans[i]); 96 } 97 printf( " \n " ); 98 } 99 100 int main() 101 { 102 freopen( " milk3.in " , " r " , stdin); 103 freopen( " milk3.out " , " w " , stdout); 104 105 int a, b, c; 106 scanf( " %d%d%d " , & A, & B, & C); 107 water.push(WATER( 0 , C)); 108 memset(use, 0 , sizeof (use)); 109 use[ 0 ][C] = true ; 110 go(); 111 }
转载于:https://www.cnblogs.com/litstrong/archive/2010/04/12/1710368.html
