题目大意：
农民约翰有三个容量分别是A,B,C升的桶，A,B,C分别是三个从1到20的整数， 最初，A和B桶都是空的，而C桶是装满牛奶的。有时，农民把牛奶从一个桶倒到 另一个桶中，直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约， 牛奶不会有丢失 写一个程序去帮助农民找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。
样例输入:
8 9 10
样例输出：
1 2 8 9 10
题解：
用搜索，把A桶是空的所有情况都标记一边，遍历完所有情况，输出。
C++ /* ID:mujinui1 PROG:milk3 LANG:C++ */ #include <fstream> #include <cstdlib> #include <algorithm> #include<cstring> using namespace std; long ans[50],p=-1; long a,b,c; //各桶上限 bool found[50][50][50]; //搜索记录 bool isIn(long C) //其实可以用置位下表c的元素来自然排序 { bool in=false; for (long i=0;i<=p;i++) { if (ans[i]==C){ in=true; break; } } return in; } void DFS(long A,long B,long C) { if (found[A][B][C]) return; found[A][B][C]=true; if (A==0){ if (!isIn(C)){ ans[++p]=C; } } if (A<=b-B) DFS(0,B+A,C); //A->B else DFS(A-(b-B),b,C); if (A<=c-C) DFS(0,B,C+A); //A->C else DFS(A-(c-C),B,c); if (B<=a-A) DFS(A+B,0,C); //B->A else DFS(a,B-(a-A),C); if (B<=c-C) DFS(A,0,C+B); //B->C else DFS(A,B-(c-C),c); if (C<=a-A) DFS(A+C,B,0); //C->A else DFS(a,B,C-(a-A)); if (C<=b-B) DFS(A,B+C,0); //C->B else DFS(A,b,C-(b-B)); return; } int main() { ifstream fin ("milk3.in"); ofstream fout ("milk3.out"); memset (ans,0,sizeof(ans)); memset (found,0,sizeof(found)); fin >>a >>b >>c; DFS(0,0,c); sort(ans,ans+p+1); for (long i=0;i<=p;i++) { if (i!=0) fout <<' '; fout <<ans[i]; } fout<<endl; return 0; }