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。

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

【代码】

 /*

 ID: icedrea1

 PROB: milk3

 LANG: C++

 */

 #include <iostream>

 #include <fstream>

 using namespace std;

 int A,B,C;

 bool p[][][];

 void go(int a,int b,int c)

 {

     //cout<<"go "<<a<<" "<<b<<" "<<c<<endl;

     int x,y,z;

     // a->b

     x=; y=a+b; z=c; if(y>B) { x=y-B; y=B; }

     if(!p[x][y][z]) { p[x][y][z]=true; go(x,y,z); }

     // a->c

     x=; y=b; z=a+c; if(z>C) { x=z-C; z=C; }

     if(!p[x][y][z]) { p[x][y][z]=true; go(x,y,z); }

     // b->a

     x=a+b; y=; z=c; if(x>A) { y=x-A; x=A; }

     if(!p[x][y][z]) { p[x][y][z]=true; go(x,y,z); }

     // b->c

     x=a; y=; z=b+c; if(z>C) { y=z-C; z=C; }

     if(!p[x][y][z]) { p[x][y][z]=true; go(x,y,z); }

     // c->a

     x=a+c; y=b; z=; if(x>A) { z=x-A; x=A; }

     if(!p[x][y][z]) { p[x][y][z]=true; go(x,y,z); }

     // c->b

     x=a; y=b+c; z=; if(y>B) { z=y-B; y=B; }

     if(!p[x][y][z]) { p[x][y][z]=true; go(x,y,z); }

 }

 int main()

 {

     ifstream in("milk3.in");

     ofstream out("milk3.out");

     in>>A>>B>>C;

     p[][][C]=true; go(,,C);

     bool can[]={};

     int a=;

     for(int b=;b<=B;++b)

         for(int c=;c<=C;++c)

             if(p[a][b][c]) can[c]=true;

     int c;

     for(c=;c<=C;++c)

         if(can[c]) { out<<c; break; }

     for(++c;c<=C;++c)

         if(can[c]) out<<" "<<c;

     out<<endl;

     in.close();

     out.close();

     return ;

 }