【USACO1.4.4】Mother's Milk 母亲的牛奶
Time Limit:10000MS Memory Limit:65536K
Total Submit:42 Accepted:27
Case Time Limit:1000MS
Description
农民约翰有三个容量分别是A,B,C升的桶,A,B,C分别是三个从1到20的整数, 最初,A和B桶都是空的,而C桶是装满牛奶的。有时,农民把牛奶从一个桶倒到 另一个桶中,直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约, 牛奶不会有丢失。
写一个程序去帮助农民找出当A桶是空的时候,C桶中牛奶所剩量的所有可能性。
Input
单独的一行包括三个整数A,B和C。
Output
只有一行,升序地列出当A桶是空的时候,C桶牛奶所剩量的所有可能性。
Sample Input
样例输入1:
8 9 10
样例输入2:
2 5 10
Sample Output
样例输出1:
1 2 8 9 10
样例输出2:
5 6 7 8 9 10
解题思路:
这道题其实一道经典的dfs倒水问题,说的就是两种倒水的情况,,直到被灌桶装满或原桶空了,一定要好好理解这句话的含义,我一开始就卡在这句话上,想到8 9 10的样例为 1 2 3 4 5 6 7 8 9 10,,,,真是SB啊。
好了,来说说倒水吧,就根据被灌桶装满和原桶为空两种情况来进行dfs就好,如果被刀捅(以后称为B桶),原桶(以后称为A桶).
如果A桶满了,但是B桶还有奶,那么这个时候的状态和B桶空了,A桶还没满是不同的。
针对这道题,由于只有3个桶,且前两个桶是空的,后一个桶是满的,那么定义(0,0,C)作为其实的状态,其实开始的时候C==c,比如拿C桶来说吧,C桶中的奶的情况数,
只可能有0,1,2,3,4,5,,,C这C+1种情况,所以我们只需要开一个record[C]的数组去存放我们需要观察的结果.
然后就是dfs了,怎么dfs呢?其实3个桶只有6种情况,也就是说c->a,c->b,a->c,a->b,b->a,b->c,依次枚举出这6种情况的dfs方案,没每次的倒奶中,又要考虑上面说的两种情况。。。。详细的就看代码吧,我第一少写了个状态,,一运行就蹦~
代码:
/* ID:wikioi_2 PROG: milk3 LANG: C++ */ # include<cstdio> # include<iostream> # include<cmath> using namespace std; # define MAX 21 int A,B,C; int rec[MAX]; int vis[MAX][MAX][MAX]; void dfs( int a,int b,int c ) { if ( vis[a][b][c] == 1 ) { return; } else { vis[a][b][c] = 1; } if ( a==0&&!rec[c] ) { rec[c] = 1; } //c->a if ( c >= A-a ) { dfs(A,b,c-A+a); } else { dfs(a+c,b,0); } //c->b if ( c >= B-b ) { dfs(a,B,c-B+b); } else { dfs(a,b+c,0); } //b->a if ( b >= A-a ) { dfs(A,b-A+a,c); } else { dfs(a+b,0,c); } //b->c if ( b >= C-c ) { dfs( a,b-C+c,C); } else { dfs( a,0,c+b ); } //a->b if ( a >= B-b ) { dfs(a-B+b,B,c); } else { dfs(0,b+a,c); } //a->c if ( a >= C-c ) { dfs(a-C+c,b,C); } else { dfs(0,b,c+a); } } int main(void) { freopen("milk3.in","r",stdin); freopen("milk3.out","w",stdout); //int A,B,C; cin>>A>>B>>C; dfs(0,0,C); int cnt = 0; for ( int i = 0;i <= C;i++ ) { if ( rec[i] ) { cnt++; if( cnt == 1 ) { cout<<i; } else { cout<<" "<<i; } } } cout<<endl; return 0; }