USACO Section1.4 Mother's Milk 解题报告

　　　　milk3解题报告 —— icedream61 博客园（转载请注明出处）
------------------------------------------------------------------------------------------------------------------------------------------------
【题目】
　　有三个桶，容量分别是A、B、C，开始C桶是满的。
　　你可以不断将某个桶的奶倒到另一个桶里，但只允许全倒过去，或者将后者倒满，前者留下剩余的奶。
　　请问，当A桶空时，C桶中的奶量可能有哪些值？
【数据范围】
　　A、B、C均为1到20的整数
【输入格式】
　　A B C
【输出格式】
　　c1 c2 c3 .. cn（表示题目所求C桶可能的容量，升序排列）
【输入样例1】
　　8 9 10
【输出样例1】
　　1 2 8 9 10
【输入样例2】
　　2 5 10
【输出样例2】
　　5 6 7 8 9 10
------------------------------------------------------------------------------------------------------------------------------------------------
【分析】
　　直接暴力搜索，别想复杂了就好。
　　三个桶所有的情况最多是20×20×20=8000种，很少的。
　　设布尔型变量p[a][b][c]表示A桶奶量a、B桶奶量b、C桶奶量c的情况是否可能达到。
　　开始，令p[0][0][C]=true;
　　而后，开始搜索，每达到一种新的状态，就从此状态把六种倒法都试过来，搜索状态最多8000种，时间完全够。
　　最后，看看p[0][b][c]的状态，让b从0取到20，看c都有可能取哪些值，记下来，按顺序输出即可。
------------------------------------------------------------------------------------------------------------------------------------------------
【总结】
　　USACO评测真严格！行尾空格不忽略。想省点代码的，第一个点就WA了……
　　第二次AC。

------------------------------------------------------------------------------------------------------------------------------------------------

【代码】

 1 /*
 2 ID: icedrea1
 3 PROB: milk3
 4 LANG: C++
 5 */
 6 
 7 #include <iostream>
 8 #include <fstream>
 9 using namespace std;
10 
11 int A,B,C;
12 bool p[21][21][21];
13 
14 void go(int a,int b,int c)
15 {
16     //cout<<"go "<<a<<" "<<b<<" "<<c<<endl;
17     int x,y,z;
18     // a->b
19     x=0; y=a+b; z=c; if(y>B) { x=y-B; y=B; }
20     if(!p[x][y][z]) { p[x][y][z]=true; go(x,y,z); }
21     // a->c
22     x=0; y=b; z=a+c; if(z>C) { x=z-C; z=C; }
23     if(!p[x][y][z]) { p[x][y][z]=true; go(x,y,z); }
24     // b->a
25     x=a+b; y=0; z=c; if(x>A) { y=x-A; x=A; }
26     if(!p[x][y][z]) { p[x][y][z]=true; go(x,y,z); }
27     // b->c
28     x=a; y=0; z=b+c; if(z>C) { y=z-C; z=C; }
29     if(!p[x][y][z]) { p[x][y][z]=true; go(x,y,z); }
30     // c->a
31     x=a+c; y=b; z=0; if(x>A) { z=x-A; x=A; }
32     if(!p[x][y][z]) { p[x][y][z]=true; go(x,y,z); }
33     // c->b
34     x=a; y=b+c; z=0; if(y>B) { z=y-B; y=B; }
35     if(!p[x][y][z]) { p[x][y][z]=true; go(x,y,z); }
36 }
37 
38 int main()
39 {
40     ifstream in("milk3.in");
41     ofstream out("milk3.out");
42 
43     in>>A>>B>>C;
44 
45     p[0][0][C]=true; go(0,0,C);
46 
47     bool can[21]={};
48     int a=0;
49     for(int b=0;b<=B;++b)
50         for(int c=0;c<=C;++c)
51             if(p[a][b][c]) can[c]=true;
52 
53     int c;
54     for(c=0;c<=C;++c)
55         if(can[c]) { out<<c; break; }
56     for(++c;c<=C;++c)
57         if(can[c]) out<<" "<<c;
58     out<<endl;
59 
60     in.close();
61     out.close();
62     return 0;
63 }