[USACO 1.4.4] Mother's Milk

[题目描述]

Mother's Milk

母亲的牛奶

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

PROGRAM NAME: milk3

INPUT FORMAT

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

SAMPLE INPUT (file milk3.in)

8 9 10

OUTPUT FORMAT

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

SAMPLE OUTPUT (file milk3.out)

1 2 8 9 10

SAMPLE INPUT (file milk3.in)

2 5 10

SAMPLE OUTPUT (file milk3.out)

5 6 7 8 9 10


[解题思路]

简单的记忆化搜索。

记f[a,b,c]为三个桶当前的状态,true则为可以到此状态,false则不行,枚举6种倒牛奶的情况,最后看f[0,c[3]-i,i]是否可达(c[3]为c桶的容量),是就输出i。


[Code]

{
ID: zane2951
PROG: milk3
LANG: PASCAL
}

program milk3;
var
   c:array[0..4] of longint;
   ans:array[0..21] of longint;
   f:array[0..21,0..21,0..21] of boolean;
   i,top:longint;

//-----------min-----------
function min(a,b:longint):longint;
begin
   if ab then exit(a) else exit(b);
end;

//-----------run-----------
procedure run(x,y,z:longint);
var
   xx,yy,zz:longint;

begin
   if f[x,y,z] then exit;
   f[x,y,z]:=true;
   if x0 then
      begin
         //-------x to y---------
         yy:=min(c[2],y+x);
         xx:=x-(yy-y);
         run(xx,yy,z);
         //-------x to z---------
         zz:=min(c[3],z+x);
         xx:=x-(zz-z);
         run(xx,y,zz);
      end;
   if y0 then
      begin
         //-------y to x---------
         xx:=min(c[1],x+y);
         yy:=y-(xx-x);
         run(xx,yy,z);
         //-------y to z---------
         zz:=min(c[3],z+y);
         yy:=y-(zz-z);
         run(x,yy,zz);
      end;
   if z0 then
      begin
         //-------z to x---------
         xx:=min(c[1],x+z);
         zz:=z-(xx-x);
         run(xx,y,zz);
         //-------z to y---------
         yy:=min(c[2],y+z);
         zz:=z-(yy-y);
         run(x,yy,zz);
      end;
end;

//----------main-----------
begin
   assign(input,'milk3.in'); reset(input);
   assign(output,'milk3.out'); rewrite(output);
   readln(c[1],c[2],c[3]);
   run(0,0,c[3]); top:=0;
   for i:=0 to c[3] do
      if f[0,c[3]-i,i] then begin inc(top); ans[top]:=i; end;
   for i:=1 to top-1 do write(ans[i],'':1);
   writeln(ans[top]);
   close(input); close(output);
end.

最新回复(0)
/jishuscDM0zcnz1Ow8t4AqJg3VacJUyr3DALeIjDYbA_3D_3D4858304
8 简首页