📄 usaco 2_1_4 healthy holsteins 题解_leokan的blog.mht
字号:
<DIV id=3Dtab><A href=3D"http://hi.baidu.com/leokan">=D6=F7=D2=B3</A><A =
class=3Don=20
href=3D"http://hi.baidu.com/leokan/blog">=B2=A9=BF=CD</A><A=20
href=3D"http://hi.baidu.com/leokan/album">=CF=E0=B2=E1</A><SPAN>|</SPAN><=
A=20
href=3D"http://hi.baidu.com/leokan/profile">=B8=F6=C8=CB=B5=B5=B0=B8</A> =
<SPAN>|</SPAN><A=20
href=3D"http://hi.baidu.com/leokan/friends">=BA=C3=D3=D1</A> =
<SPAN>|</SPAN><A=20
href=3D"http://hi.baidu.com/leokan/modify/spbasic/0">=C9=E8=D6=C3</A> =
</DIV></DIV>
<DIV class=3Dstage>
<DIV class=3Dstagepad>
<DIV style=3D"WIDTH: 100%">
<TABLE class=3Dmodth cellSpacing=3D0 cellPadding=3D0 width=3D"100%" =
border=3D0>
<TBODY>
<TR>
<TD class=3Dmodtl width=3D7> </TD>
<TD class=3Dmodtc noWrap>
<DIV class=3Dmodhead><SPAN =
class=3Dmodtit>=B2=E9=BF=B4=CE=C4=D5=C2</SPAN></DIV></TD>
<TD class=3Dmodtc noWrap align=3Dright>
<DIV class=3Dmodopt><A class=3Dmodact=20
href=3D"http://hi.baidu.com/leokan/creat/blog/"><IMG=20
src=3D"http://img.baidu.com/hi/img/ico_postnew.gif" =
align=3DabsMiddle=20
border=3D0>=D0=B4=D0=C2=CE=C4=D5=C2</A></DIV></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 2.1.4 Healthy Holsteins =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C228=C8=D5 =D0=C7=C6=DA=D2=BB =
12:02</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 2.1.4 Healthy Holsteins</H2>
<DIV class=3Dt_msgfont>Healthy Holsteins<BR>Burch & Kolstad =
<BR>Farmer=20
John prides himself on having the healthiest dairy cows in the =
world. He=20
knows the vitamin content for one scoop of each feed type and the =
minimum=20
daily vitamin requirement for the cows. Help Farmer John feed his =
cows so=20
they stay healthy while minimizing the number of scoops that a cow =
is fed.=20
<BR><BR>Given the daily requirements of each kind of vitamin that =
a cow=20
needs, identify the smallest combination of scoops of feed a cow =
can be=20
fed in order to meet at least the minimum vitamin requirements.=20
<BR><BR>Vitamins are measured in integer units. Cows can be fed at =
most=20
one scoop of any feed type. It is guaranteed that a solution =
exists for=20
all contest input data. <BR><BR>PROGRAM NAME: holstein<BR>INPUT=20
FORMAT<BR>Line 1: integer V (1 <=3D V <=3D 25), =
the number=20
of types of vitamins <BR>Line 2: V integers =
(1=20
<=3D each one <=3D 1000), the minimum requirement for each =
of the V=20
vitamins that a cow requires each day <BR>Line =
3: =20
integer G (1 <=3D G <=3D 15), the number of types of feeds=20
available <BR>Lines 4..G+3: V integers (0 =
<=3D=20
each one <=3D 1000), the amount of each vitamin that one scoop =
of this=20
feed contains. The first line of these G lines describes feed #1; =
the=20
second line describes feed #2; and so =
on. <BR><BR>SAMPLE INPUT=20
(file holstein.in) <BR>4<BR>100 200 300 400<BR>3<BR>50 =
50 =20
50 50<BR>200 300 200 300<BR>900 150 389 =
399<BR><BR>OUTPUT=20
FORMAT<BR>The output is a single line of output that contains: =
<BR><BR>the=20
minimum number of scoops a cow must eat, followed by: <BR>a SORTED =
<SPAN=20
class=3Dt_tag href=3D"tag.php?name=3Dlis">lis</SPAN>t (from =
smallest to largest)=20
of the feed types the cow is given <BR>SAMPLE OUTPUT (file=20
holstein.out)<BR>2 1 3<BR><BR><BR><BR>Healthy Holsteins=20
=
<BR><BR>=BD=A1=BF=B5=B5=C4=BA=C3=CB=B9=CC=B9=C4=CC=C5=A3<BR><BR>=D2=EB =
by caszhao=20
=
(QQ:9696421)<BR><BR>=C5=A9=C3=F1JOHN=D2=D4=D3=B5=D3=D0=CA=C0=BD=E7=C9=CF=D7=
=EE=BD=A1=BF=B5=B5=C4=C4=CC=C5=A3=CE=AA=BD=BE=B0=C1=A1=A3=CB=FB=D6=AA=B5=C0=
=C3=BF=D6=D6=CB=C7=C1=CF=D6=D0=CB=F9=B0=FC=BA=AC=B5=C4=B5=C4=C5=A3=CB=F9=D0=
=E8=B5=C4=D7=EE=B5=CD=B5=C4=CE=AC=CB=FB=C3=FC=C1=BF=CA=C7=B6=E0=C9=D9=A1=A3=
=C7=EB=C4=E3=B0=EF=D6=FA=C5=A9=B7=F2=CE=B9=D1=F8=CB=FB=B5=C4=C5=A3=A3=AC=D2=
=D4=B1=A3=B3=D6=CB=FB=C3=C7=B5=C4=BD=A1=BF=B5=A3=AC=CA=B9=CE=B9=B8=F8=C5=A3=
=B5=C4=CB=C7=C1=CF=B5=C4=D6=D6=CA=FD=D7=EE=C9=D9=A1=A3<BR>=B8=F8=B3=F6=C5=
=A3=CB=F9=D0=E8=B5=C4=D7=EE=B5=CD=B5=C4=CE=AC=CB=FB=C3=FC=A3=AC=CA=E4=B3=F6=
=CE=B9=B8=F8=C5=A3=D0=E8=D2=AA=C4=C4=D0=A9=D6=D6=C0=E0=B5=C4=CB=C7=C1=CF=A3=
=AC=C7=D2=CB=F9=D0=E8=B5=C4=D6=D6=C0=E0=CA=FD=D7=EE=C9=D9=A1=A3<BR><BR>PR=
OGRAM=20
NAME: holstein<BR>INPUT=20
=
FORMAT<BR>=B5=DA1=D0=D0=A3=BA=D2=BB=B8=F6=D5=FB=CA=FDV(1<=3DV<=3D25=
)=A3=AC=B1=ED=CA=BE=D0=E8=D2=AA=B5=C4=CE=AC=CB=FB=C3=FC=B5=C4=D6=D6=C0=E0=
=CA=FD=A1=A3<BR>=B5=DA2=D0=D0=A3=BAV=B8=F6=D5=FB=CA=FD(1<=3D=C3=BF=B8=F6=
=CA=FD<=3D1000)=A3=AC=B1=ED=CA=BE=C5=A3=C3=BF=CC=EC=D0=E8=D2=AA=B5=C4=CE=
=AC=CB=FB=C3=FC=B5=C4=D7=EE=D0=A1=C1=BF=A1=A3<BR>=B5=DA3=D0=D0=A3=BA=D2=BB=
=B8=F6=D5=FB=CA=FDG(1<=3DG<=3D15)=A3=AC=B1=ED=CA=BE=BF=C9=D3=C3=C0=B4=
=CE=B9=C5=A3=B5=C4=CB=C7=C1=CF=B5=C4=CA=FD=C1=BF=A1=A3=CF=C2=C3=E6G=D0=D0=
=A3=AC=B5=DAi=D0=D0=B1=ED=CA=BE=B1=E0=BA=C5=CE=AAi=CB=C7=C1=CF=B0=FC=BA=AC=
=B5=C4=B8=F7=D6=D6=CE=AC=CB=FB=C3=FC=B5=C4=C1=BF=B5=C4=B6=E0=C9=D9=A1=A3<=
BR><BR>SAMPLE=20
INPUT (file holstein.in)<BR>4<BR>100 200 300 400<BR>3<BR>50 50 50=20
50<BR>200 300 200 300<BR>900 150 389 399<BR><BR>OUTPUT=20
=
FORMAT<BR>=CA=E4=B3=F6=CE=C4=BC=FE=D6=BB=D3=D0=D2=BB=D0=D0=A3=AC=B0=FC=C0=
=A8=A3=BA<BR><BR>=C5=A3=B1=D8=D0=E8=B5=C4=D7=EE=D0=A1=B5=C4=CB=C7=C1=CF=D6=
=D6=CA=FDP =
<BR>=BA=F3=C3=E6=D3=D0P=B8=F6=CA=FD=A3=AC=B1=ED=CA=BE=CB=F9=D1=A1=D4=F1=B5=
=C4=CB=C7=C1=CF=B1=E0=BA=C5=A3=A8=B0=B4=B4=D3=D0=A1=B5=BD=B4=F3=C5=C5=C1=D0=
=A3=A9=A1=A3=20
<BR>SAMPLE OUTPUT (file holstein.out)<BR>2 1 3</DIV>
<P></P>
<HR>
<P></P>
<P><STRONG>USACO 2.1.4 Healthy =
Holsteins<BR>=CC=E1=BD=BB=B4=CE=CA=FD=A3=BA2=B4=CE</STRONG></P>
=
<P><STRONG>=D3=C3dfs=C3=B6=BE=D9=A1=A3=D5=E2=B5=C0=CC=E2=B2=BB=C4=D1=A3=AC=
=B5=AB=CA=C7=CC=E2=C4=BF=CE=D2=BF=B4=C1=CB=BA=DC=BE=C3=B2=C5=BF=B4=C3=F7=B0=
=D7=CA=B2=C3=B4=D2=E2=CB=BC=A3=AC=CE=D2=CF=EB=B5=C4=CC=AB=B8=B4=D4=D3=C1=CB=
=A3=AC=CE=D2=CF=EB=B5=BD=C3=BF=D2=BB=D6=D6=A3=A8BS=D2=BB=CF=C2=B7=AD=D2=EB=
=B5=C4=C8=CB=A3=AC=C3=BF=D6=D6=D6=BB=C4=DC=D3=C3=D2=BB=B4=CE=BE=CD=B2=BB=D2=
=AA=D3=C3=A1=B0=D6=D6=A1=B1=D5=E2=B8=F6=D7=D6=C2=EF=A3=A9=BF=C9=D2=D4=D3=C3=
=CE=DE=CA=FD=B4=CE=A3=AC=BB=B9=CF=EB=B5=BD=D3=C5=CF=C8=CA=E4=B3=F6=CB=C7=C1=
=CF=D7=DC=C1=BF=D7=EE=C9=D9=B5=C4=C4=C7=D2=BB=B8=F6......=C6=E4=CA=B5=CA=B2=
=C3=B4=B6=BC=B2=BB=D3=C3=A3=AC=CA=E4=B3=F6=C2=FA=D7=E3=B5=C4=BE=CD=CA=C7=C1=
=CB=A1=A3</STRONG></P>
<P><STRONG>{<BR>TASK:holstein<BR>LANG:PASCAL<BR>}<BR>program=20
holstein;<BR>type<BR> arr=3Darray[1..25] of=20
integer;<BR>var<BR> chosen,ans:array[1..16] of=20
integer;<BR> =
v,g,p,min:integer;<BR> =20
goal,temp:arr;<BR> feed:array[1..15,1..25] of=20
integer;<BR>procedure init;<BR>var<BR> =20
i,j:integer;<BR>begin<BR> =20
assign(input,'holstein.in');reset(input);<BR> =20
readln(v);<BR> for j:=3D1 to v=20
do<BR> =20
read(goal[j]);<BR> readln;<BR> =
readln(g);<BR> for i:=3D1 to g=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
for j:=3D1 to v=20
=
do<BR> &=
nbsp; =20
=
read(feed[i,j]);<BR>  =
; =20
readln;<BR> =20
end;<BR> close(input);<BR>end;<BR>procedure=20
dfs(x:integer);<BR>var<BR> =20
i,j,k:integer;<BR> =20
t:boolean;<BR>begin<BR> =20
chosen[x]:=3D1;<BR> =
inc(p);<BR> for i:=3D1=20
to v do<BR> =20
inc(temp[i],feed[x,i]);<BR> =20
t:=3Dtrue;<BR> for i:=3D1 to v=20
do<BR> if =
temp[i]<goal[i]=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
=
t:=3Dfalse;<BR> &nbs=
p; =20
=
break;<BR> &nb=
sp;=20
end;<BR> if t=20
then<BR> =20
=
begin<BR> &nbs=
p;=20
if p<min=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
min:=3Dp;<BR> =
=20
=
ans:=3Dchosen;<BR> &=
nbsp; =20
=
ans[0]:=3Dp;<BR> &nb=
sp; =20
end;<BR> =20
end<BR> else if x<g =
then=20
dfs(x+1);<BR> =
chosen[x]:=3D0;<BR> =20
dec(p);<BR> for i:=3D1 to v=20
do<BR> =20
dec(temp[i],feed[x,i]);<BR> if x<g then=20
dfs(x+1);<BR>end;<BR>procedure work;<BR>var<BR> =20
i,j:integer;<BR>begin<BR> =20
=
assign(output,'holstein.out');rewrite(output);<BR> =20
fillchar(chosen,sizeof(chosen),0);<BR> =20
fillchar(temp,sizeof(temp),0);<BR> =20
p:=3D0;<BR> min:=3Dg+1;<BR> =20
dfs(1);<BR> write(ans[0]);<BR> =
for=20
i:=3D1 to 15 do if ans[i]=3D1 then write(' =
',i);<BR> =20
writeln;<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> work;<BR>end.</STRONG></P><STRONG>
<HR>
</STRONG>
=
<P><STRONG>USACO=B5=C4=B7=D6=CE=F6=A3=AC=D2=B2=CA=C7=C3=B6=BE=D92<SUP>15<=
/SUP> possible `feed =A1=A3</STRONG></P>
<P><STRONG>Since there are only 15 feeds, and for each feed we can =
either=20
give zero or one scopes of it, there are 2<SUP>15</SUP> possible =
`feed=20
mixtures' the cows can be fed, which is only 32,768. Therefore, =
try all=20
combinations and pick which of the legal combinations uses the =
least=20
number of feeds. </STRONG></P><PRE><STRONG>#include =
<stdio.h>
#include <assert.h>
#define MAXV 25
#define MAXF 15
int req[MAXV]; /* the vitamin requirements */
int numv; /* number of vitamins */
int feeds[MAXF][MAXV]; /* the vitamin within each feed */
int numf; /* number of feeds */
int best; /* the minimum number of feeds to use found thus far */
int bestf[MAXF]; /* the set */
int curf[MAXF]; /* the current set of feeds being considered */
void find_feed(int fcnt, int fid)
{ /* fcnt is the number of feeds in the current mixture,
fid is the identifier of the first feed to try adding (last feed + =
1) */
int lv;
/* check if the requirement has been met */
for (lv =3D 0; lv < numv; lv++)
if (req[lv] > 0) break;=20
if (lv >=3D numv)
{ /* all the requirements are met */
/* we know this is better, since we wouldn't have checked it =
otherwise
(see below) */
best =3D fcnt;
for (lv =3D 0; lv < best; lv++)
bestf[lv] =3D curf[lv];
return;
}
while (fid < numf && fcnt+1 < best)
{ /* try adding each feed to the mixture */
/* the fcnt+1 < best ensures that we stop if there's no hope
in finding a better solution than one found already */
/* add the vitamins from this feed */
for (lv =3D 0; lv < numv; lv++)
req[lv] -=3D feeds[fid][lv];=20
curf[fcnt] =3D fid; /* put it in the list */
find_feed(fcnt+1, fid+1);=20
/* undo adding the vitamins */
for (lv =3D 0; lv < numv; lv++)
req[lv] +=3D feeds[fid][lv];
/* next feed */
fid++;
}
}
int main(void)=20
{
FILE *fin, *fout;
int lv, lv2;
fin =3D fopen("holstein.in", "r");
fout =3D fopen("holstein.out", "w");
assert(fin);
assert(fout);
fscanf (fin, "%d", &numv);
for (lv =3D 0; lv < numv; lv++)
fscanf (fin, "%d", &req[lv]);
fscanf (fin, "%d", &numf);
for (lv =3D 0; lv < numf; lv++)
for (lv2 =3D 0; lv2 < numv; lv2++)
fscanf (fin, "%d", &feeds[lv][lv2]);
best =3D numf+1;
find_feed(0, 0);
fprintf (fout, "%i", best);
for (lv =3D 0; lv < best; lv++)=20
fprintf (fout, " %i", bestf[lv]+1);
fprintf (fout, "\n");
return 0;
}</STRONG></PRE></DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
href=3D"http://hi.baidu.com/leokan/modify/blog/b5895160075703db8cb10ddf">=
=B1=E0=BC=AD</A> |=20
<A onclick=3D"return blogdel('blogdelform')"=20
href=3D"http://hi.baidu.com/leokan/blog/item/b5895160075703db8cb10ddf.htm=
l#">=C9=BE=B3=FD</A>=20
<FORM id=3Dblogdelform style=3D"DISPLAY: none" name=3Dblogdelform=20
action=3D/leokan/commit method=3Dpost><INPUT type=3Dhidden value=3D1 =
name=3Dct><INPUT=20
type=3Dhidden value=3D3 name=3Dcm><INPUT type=3Dhidden =
value=3Db5895160075703db8cb10ddf=20
name=3DspBlogID><INPUT type=3Dhidden =
value=3Dhttp://hi.baidu.com/leokan/blog=20
name=3DspRefURL></FORM>
<SCRIPT language=3Djavascript>
<!--
function blogdel(str)
{
var pop=3Dnew Popup({ =
contentType:3,isReloadOnClose:false,width:340,height:80});
pop.setContent("title","=C9=BE=B3=FD=CE=C4=D5=C2");
=
pop.setContent("confirmCon","=C4=FA=C8=B7=B6=A8=D2=AA=B3=B9=B5=D7=C9=BE=B3=
=FD=D5=E2=C6=AA=CE=C4=D5=C2=BC=B0=C6=E4=CB=F9=D3=D0=C6=C0=C2=DB=C2=F0=A3=BF=
");
pop.setContent("callBack",delCallback);
pop.setContent("parameter",{fid:str,popup:pop});
pop.build();
pop.show();
return false;
}
function delCallback(para)
{
var o_pop=3Dpara["popup"];
o_pop.config.contentType=3D1;
o_pop.setContent("contentUrl","");
o_pop.reBuild();
G(para["fid"]).target=3Do_pop.iframeIdName;
eval("document."+para["fid"]).submit();
}
//-->
</SCRIPT>
| <A =
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
onclick=3D"return addToFavor();"=20
href=3D"http://cang.baidu.com/do/add" =
target=3D_blank>=CC=ED=BC=D3=B5=BD=CB=D1=B2=D8</A> | =E4=AF=C0=C0(<SPAN=20
id=3Dresult></SPAN>) | <A=20
href=3D"http://hi.baidu.com/leokan/blog/item/b5895160075703db8cb10ddf.htm=
l#send">=C6=C0=C2=DB</A> (0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'USACO 2.1.3 Sorting a Three-Valued Sequence =
=CC=E2=BD=E2', 'USACO 2.1.3 Sorting a =
Three-Va...','/leokan/blog/item/03feff1f625f3667f724e477.html'];
var post =3D [true,'USACO 2.1.5 Hamming Codes =CC=E2=BD=E2','USACO 2.1.5 =
Hamming Codes =CC=E2=BD=E2', =
'/leokan/blog/item/ff9c6660d31cd940ebf8f888.html'];
if(pre[0] || post[0]){
document.write('<div =
style=3D"height:5px;line-height:5px;"> </div><div id=3D"in_nav">');
if(pre[0]){
document.write('=C9=CF=D2=BB=C6=AA=A3=BA<a href=3D"' + pre[3] + '" =
title=3D"' + pre[1] + '">' + pre[2] + '</a> ');
}
if(post[0]){
document.write('=CF=C2=D2=BB=C6=AA=A3=BA<a href=3D"' + post[3] + '" =
title=3D"' + post[1] + '">' + post[2] + '</a>');
}
document.write('</div>');
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -