usaco1.44Mother's Milk

刚开始理解错题意了，写了半天的dfs，直接delete。
写的挺多，不是太复杂，对于每种状态枚举6种情况。
View Code
  1 /*
  2    ID: your_id_here
  3    PROG: milk3
  4    LANG: C++
  5    */
  6 #include <iostream>
  7 #include<cstdio>
  8 #include<cstring>
  9 #include<algorithm>
 10 using namespace std;
 11 int a,b,c,num[50],f[30][30][30],ff[50],g;
 12 void dfs(int aa,int bb,int cc)
 13 {
 14     int d1,d2,d3,d;
 15     if(f[aa][bb][cc])
 16     return ;
 17     d1 = a-aa;
 18     d2 = b-bb;
 19     d3 = c-cc;
 20     f[aa][bb][cc] = 1;
 21     if(cc-d1>0)
 22     {
 23         cc-=d1;
 24         aa+=d1;
 25         if(aa==0&&!ff[cc])
 26         {
 27             g++;
 28             ff[cc] = 1;
 29             num[g] = cc;
 30         }
 31         dfs(aa,bb,cc);
 32         cc+=d1;
 33         aa-=d1;
 34     }
 35     else
 36     if(aa+cc<=a)
 37     {
 38         d = cc;
 39         cc = 0;
 40         aa+=d;
 41         dfs(aa,bb,cc);
 42         cc+=d;
 43         aa-=d;
 44     }
 45     if(cc-d2>0)
 46     {
 47         cc-=d2;
 48         bb+=d2;
 49         if(aa==0&&!ff[cc])
 50         {
 51             g++;
 52             ff[cc] = 1;
 53             num[g] = cc;
 54         }
 55         dfs(aa,bb,cc);
 56         cc+=d2;
 57         bb-=d2;
 58     }
 59     else
 60     if(cc+bb<=b)
 61     {
 62         d = cc;
 63         cc = 0;
 64         bb+=d;
 65         dfs(aa,bb,cc);
 66         cc+=d;
 67         bb-=d;
 68     }
 69     if(bb-d1>0)
 70     {
 71         bb-=d1;
 72         aa+=d1;
 73         if(aa==0&&!ff[cc])
 74         {
 75             g++;
 76             ff[cc] = 1;
 77             num[g] = cc;
 78         }
 79         dfs(aa,bb,cc);
 80         bb+=d1;
 81         aa-=d1;
 82     }
 83     else
 84     if(bb+aa<=a)
 85     {
 86         d = bb;
 87         bb = 0;
 88         aa+=d;
 89         if(aa==0&&!ff[cc])
 90         {
 91             g++;
 92             ff[cc] = 1;
 93             num[g] = cc;
 94         }
 95         dfs(aa,bb,cc);
 96         bb+=d;
 97         aa-=d;
 98     }
 99     if(bb-d3>0)
100     {
101         bb-=d3;
102         cc+=d3;
103         if(!ff[cc])
104         {
105             g++;
106             ff[cc] = 1;
107             num[g] = cc;
108         }
109         dfs(aa,bb,cc);
110         bb+=d3;
111         cc-=d3;
112     }
113     else
114     if(bb+cc<=c)
115     {
116         d = bb;
117         bb = 0;
118         cc+=d;
119         if(aa==0&&!ff[cc])
120         {
121             g++;
122             ff[cc] = 1;
123             num[g] = cc;
124         }
125         dfs(aa,bb,cc);
126         bb+=d;
127         cc-=d;
128     }
129     if(aa-d2>0)
130     {
131         aa-=d2;
132         bb+=d2;
133         if(aa==0&&!ff[cc])
134         {
135             g++;
136             ff[cc] = 1;
137             num[g] = cc;
138         }
139         dfs(aa,bb,cc);
140         aa+=d2;
141         bb-=d2;
142     }
143     else
144     if(aa+bb<=b)
145     {
146         d = aa;
147         aa = 0;
148         bb+=d;
149         if(aa==0&&!ff[cc])
150         {
151             g++;
152             ff[cc] = 1;
153             num[g] = cc;
154         }
155         dfs(aa,bb,cc);
156         aa+=d;
157         bb-=d;
158     }
159     if(aa-d3>0)
160     {
161         aa-=d3;
162         cc+=d3;
163         if(aa==0&&!ff[cc])
164         {
165             g++;
166             ff[cc] = 1;
167             num[g] = cc;
168         }
169         dfs(aa,bb,cc);
170         aa+=d3;
171         cc-=d3;
172     }
173     else
174     if(aa+cc<=c)
175     {
176         d = aa;
177         aa = 0;
178         cc+=d;
179         if(aa==0&&!ff[cc])
180         {
181             g++;
182             ff[cc] = 1;
183             num[g] = cc;
184         }
185         dfs(aa,bb,cc);
186         aa+=d;
187         cc-=d;
188     }
189 }
190 int main()
191 {
192     freopen("milk3.in","r",stdin);
193     freopen("milk3.out","w",stdout);
194     int i,aa,bb,cc;
195     cin>>a>>b>>c;
196     aa = 0;
197     bb = 0;
198     cc = c;
199     dfs(aa,bb,cc);
200     sort(num+1,num+g+1);
201     for(i= 1 ; i <= g ; i++)
202     {
203         if(i!=1)
204         cout<<" ";
205         cout<<num[i];
206     }
207     puts("");
208     fclose(stdin);
209     fclose(stdout);
210     return 0;
211 }