[USACO1.4]母亲的牛奶 Mother's Milk

题目描述

农民约翰有三个容量分别是A,B,C升的桶，A,B,C分别是三个从1到20的整数，最初，A和B桶都是空的，而C桶是装满牛奶的。有时，农民把牛奶从一个桶倒到另一个桶中，直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约，牛奶不会有丢失。

写一个程序去帮助农民找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。

输入格式

单独的一行包括三个整数A,B和C。

输出格式

只有一行，升序地列出当A桶是空的时候，C桶牛奶所剩量的所有可能性。

输入输出样例

输入 #1

8 9 10

1 2 8 9 10

输入 #2

2 5 10

输出 #2

5 6 7 8 9 10

说明/提示

题目翻译来自NOCOW。

USACO Training Section 1.4

【解题思路】

DFS暴力枚举所有情况。

A可以倒给B和C

B可以倒给A和C

C可以倒给A和B

【code】

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5 int A,B,C;
 6 bool w[50],vis[50][50];
 7 inline int Min(int a,int b){
 8     return a<b?a:b;
 9 }
10 inline void DFS(int a,int c){
11     int b=C-a-c;
12     if(vis[a][c])return ;
13     vis[a][c]=true;
14     if(a==0)w[c]=true;
15     if(a!=0&&B!=b)DFS(a-Min(a,B-b),c);//a->b
16     if(a!=0&&C!=c)DFS(a-Min(a,C-c),c+Min(a,C-c));//a->c
17     if(b!=0&&A!=a)DFS(a+Min(b,A-a),c);//b->a
18     if(b!=0&&C!=c)DFS(a,c+Min(b,C-c));//b->c
19     if(c!=0&&A!=a)DFS(a+Min(c,A-a),c-Min(c,A-a));//c->a
20     if(c!=0&&B!=b)DFS(a,c-Min(c,B-b));//c->b
21     return ;
22 }
23 int main(){
24     //freopen("1215.in","r",stdin);
25     //freopen("1215.out","w",stdout);
26     scanf("%d%d%d",&A,&B,&C);
27     DFS(0,C);
28     for(register int i=0;i<=C;i++)
29         if(w[i])printf("%d ",i);
30     return 0;
31 }