📄 usaco 3_1_6 stamps 题解_leokan的blog.mht
字号:
<DIV class=3Ddate>2008=C4=EA02=D4=C202=C8=D5 =D0=C7=C6=DA=C1=F9 =
10:33</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 3.1.6 Stamps</H2>
<DIV class=3Dt_msgfont>Stamps<BR><BR>Given a set of N stamp values =
(e.g., {1=20
cent, 3 cents}) and an upper limit K to the number of stamps that =
can fit=20
on an envelope, calculate the largest unbroken <SPAN class=3Dt_tag =
href=3D"tag.php?name=3Dlis">lis</SPAN>t of postages from 1 cent to =
M cents=20
that can be created. <BR><BR>For example, consider stamps whose =
values are=20
limited to 1 cent and 3 cents; you can use at most 5 stamps. It's =
easy to=20
see how to assemble postage of 1 through 5 cents (just use that =
many 1=20
cent stamps), and successive values aren't much harder: <BR><BR>6 =
=3D 3 + 3=20
<BR>7 =3D 3 + 3 + 1 <BR>8 =3D 3 + 3 + 1 + 1 <BR>9 =3D 3 + 3 + 3 =
<BR>10 =3D 3 + 3 +=20
3 + 1 <BR>11 =3D 3 + 3 + 3 + 1 + 1 <BR>12 =3D 3 + 3 + 3 + 3 <BR>13 =
=3D 3 + 3 + 3=20
+ 3 + 1. <BR>However, there is no way to make 14 cents of postage =
with 5=20
or fewer stamps of value 1 and 3 cents. Thus, for this set of two =
stamp=20
values and a limit of K=3D5, the answer is M=3D13. <BR><BR>The =
most difficult=20
test case for this problem has a time limit of 4 seconds. =
<BR><BR>PROGRAM=20
NAME: stamps<BR>INPUT FORMAT<BR>Line 1: Two integers K =
and N.=20
K (1 <=3D K <=3D 200) is the total number of stamps that can =
be used. N=20
(1 <=3D N <=3D 50) is the number of stamp =
values. <BR>Lines=20
2..end: N integers, 15 per line, listing all of the N stamp =
values, each=20
of which will be at most 10000. <BR><BR>SAMPLE INPUT =
(file=20
stamps.in)<BR>5 2<BR>1 3<BR><BR>OUTPUT FORMAT<BR>Line 1: One =
integer, the=20
number of contiguous postage values starting at 1 cent that can be =
formed=20
using no more than K stamps from the set. <BR><BR>SAMPLE OUTPUT =
(file=20
stamps.out)<BR>13<BR><BR><BR><BR>Stamps =
<BR>=D3=CA=C6=B1<BR><BR>=D2=EB by Felicia=20
Crazy<BR><BR><BR>=D2=D1=D6=AA=D2=BB=B8=F6 N =
=C3=B6=D3=CA=C6=B1=B5=C4=C3=E6=D6=B5=BC=AF=BA=CF=A3=A8=C8=E7=A3=AC{1 =
=B7=D6=A3=AC3 =B7=D6}=A3=A9=BA=CD=D2=BB=B8=F6=C9=CF=CF=DE K =A1=AA=A1=AA =
=B1=ED=CA=BE=D0=C5=B7=E2=C9=CF=C4=DC=B9=BB=CC=F9 K =
=D5=C5=D3=CA=C6=B1=A1=A3=BC=C6=CB=E3=B4=D3=20
1 =B5=BD M =
=B5=C4=D7=EE=B4=F3=C1=AC=D0=F8=BF=C9=CC=F9=B3=F6=B5=C4=D3=CA=D7=CA=A1=A3 =
<BR><BR>=C0=FD=C8=E7=A3=AC=BC=D9=C9=E8=D3=D0 1 =B7=D6=BA=CD 3 =
=B7=D6=B5=C4=D3=CA=C6=B1=A3=BB=C4=E3=D7=EE=B6=E0=BF=C9=D2=D4=CC=F9 5 =
=D5=C5=D3=CA=C6=B1=A1=A3=BA=DC=C8=DD=D2=D7=CC=F9=B3=F6 1 =B5=BD 5=20
=B7=D6=B5=C4=D3=CA=D7=CA=A3=A8=D3=C3 1 =
=B7=D6=D3=CA=C6=B1=CC=F9=BE=CD=D0=D0=C1=CB=A3=A9=A3=AC=BD=D3=CF=C2=C0=B4=B5=
=C4=D3=CA=D7=CA=D2=B2=B2=BB=C4=D1=A3=BA <BR><BR>6 =3D 3 + 3 <BR>7 =3D 3 =
+ 3 + 1 <BR>8 =3D 3=20
+ 3 + 1 + 1 <BR>9 =3D 3 + 3 + 3 <BR>10 =3D 3 + 3 + 3 + 1 <BR>11 =
=3D 3 + 3 + 3 +=20
1 + 1 <BR>12 =3D 3 + 3 + 3 + 3 <BR>13 =3D 3 + 3 + 3 + 3 + 1=A1=A3 =
<BR>=C8=BB=B6=F8=A3=AC=CA=B9=D3=C3 5 =C3=B6 1=20
=B7=D6=BB=F2=D5=DF 3 =
=B7=D6=B5=C4=D3=CA=C6=B1=B8=F9=B1=BE=B2=BB=BF=C9=C4=DC=CC=F9=B3=F6 14 =
=B7=D6=B5=C4=D3=CA=D7=CA=A1=A3=D2=F2=B4=CB=A3=AC=B6=D4=D3=DA=D5=E2=C1=BD=D6=
=D6=D3=CA=C6=B1=B5=C4=BC=AF=BA=CF=BA=CD=C9=CF=CF=DE =
K=3D5=A3=AC=B4=F0=B0=B8=CA=C7 M=3D13=A1=A3 <BR><BR>PROGRAM=20
NAME: stamps<BR>INPUT FORMAT<BR>=B5=DA 1 =D0=D0=A3=BA =
=C1=BD=B8=F6=D5=FB=CA=FD=A3=ACK =BA=CD N=A1=A3K=A3=A81 <=3D K=20
<=3D =
200=A3=A9=CA=C7=BF=C9=D3=C3=B5=C4=D3=CA=C6=B1=D7=DC=CA=FD=A1=A3N=A3=A81 =
<=3D N <=3D =
50=A3=A9=CA=C7=D3=CA=C6=B1=C3=E6=D6=B5=B5=C4=CA=FD=C1=BF=A1=A3 =
<BR>=B5=DA 2 =D0=D0 ..=20
=CE=C4=BC=FE=C4=A9=A3=BA N =
=B8=F6=D5=FB=CA=FD=A3=AC=C3=BF=D0=D0 15 =
=B8=F6=A3=AC=C1=D0=B3=F6=CB=F9=D3=D0=B5=C4 N =
=B8=F6=D3=CA=C6=B1=B5=C4=C3=E6=D6=B5=A3=AC=C3=E6=D6=B5=B2=BB=B3=AC=B9=FD =
10000=A1=A3 <BR><BR>SAMPLE=20
INPUT (file stamps.in)<BR>5 2<BR>1 3<BR><BR>OUTPUT =
FORMAT<BR>=B5=DA 1=20
=D0=D0=A3=BA<BR>=D2=BB=B8=F6=D5=FB=CA=FD=A3=AC=B4=D3 1 =
=B7=D6=BF=AA=CA=BC=C1=AC=D0=F8=B5=C4=BF=C9=D3=C3=BC=AF=BA=CF=D6=D0=B2=BB=B6=
=E0=D3=DA K =D5=C5=D3=CA=C6=B1=CC=F9=B3=F6=B5=C4=D3=CA=D7=CA=CA=FD=A1=A3 =
<BR><BR>SAMPLE OUTPUT (file=20
stamps.out)<BR>13</DIV>
<P></P>
<HR>
<P></P>
<P>USACO 3.1.6 Stamps<BR>=CC=E1=BD=BB=B4=CE=CA=FD:2=B4=CE</P>
=
<P>=D3=D6=CA=C7=B3=F6=CF=D6=C1=CB=B6=C1=C8=A1=C1=CB=CA=FD=D7=E9=B7=B6=CE=A7=
=D2=D4=CD=E2=B5=C4=CA=FD,=CE=D2=B5=C4=B5=E7=C4=D4=C4=C7=C0=EF=B6=C1=C1=CB=
0,USACO=B2=BB=D6=AA=B6=C1=C1=CB=CA=B2=C3=B4,=B5=BC=D6=C2=CE=D2=D5=E2=C0=EF=
=CA=E4=B3=F613=CB=FC=C6=AB=CB=B5=CE=D2=CA=E4=B3=F615.<BR>=B6=AF=CC=AC=B9=E6=
=BB=AE...f(x)=3Dmin{f(x-stamp[i])}i=A1=CA{1..n}f(x)=B1=ED=CA=BE=C8=A1=B5=BD=
x=D5=E2=B8=F6=C3=E6=D6=B5=D7=EE=C9=D9=B5=C4=D3=CA=C6=B1=CA=FD.</P>
<P>{<BR>TASK:stamps<BR>LANG:PASCAL<BR>}<BR>program=20
stamps;<BR>var<BR> f:array[0..2000000] of=20
integer;<BR> stamp:array[1..50] of=20
integer;<BR> n,k:integer;<BR>procedure=20
init;<BR>var<BR> =20
i:integer;<BR>begin<BR> =20
assign(input,'stamps.in');reset(input);<BR> =20
readln(k,n);<BR> for i:=3D1 to n do=20
read(stamp[i]);<BR> =
close(input);<BR>end;<BR>procedure=20
dp;<BR>var<BR> =20
i,j,max:longint;<BR>begin<BR> =20
assign(output,'stamps.out');rewrite(output);<BR> =
{writeln(k,' ',n);<BR> for i:=3D1 to n do=20
write(stamp[i]);}<BR> =20
fillchar(f,sizeof(f),0);<BR> for i:=3D1 to =
2000000=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
f[i]:=3Dmaxint;<BR> =
=20
for j:=3D1 to n=20
=
do<BR> &=
nbsp; =20
if i-stamp[j]>=3D0=20
=
then<BR>  =
; =20
if f[i-stamp[j]]+1<f[i]=20
=
then<BR>  =
; =
=20
=
f[i]:=3Df[i-stamp[j]]+1;<BR> &nb=
sp; =20
if f[i]>k then =
break;<BR> =20
end;<BR> writeln(i-1);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> dp;<BR>end.</P>
<HR>
<P>USACO=B5=C4=B7=D6=CE=F6</P>
<P>This problem is simply begging for a DP solution. We keep an =
array=20
"minstamps" such that minstamps[i] is the minimum number of stamps =
needed=20
to make i cents. For each stamp type, we try adding one stamp of =
that type=20
to each number of cents that we have already made. After we have =
found the=20
minimum number of stamps needed to make any given number of cents, =
we find=20
the smallest number of cents that we cannot make with the given =
number of=20
stamps, and then we output one less then that.</P><PRE>#include =
<fstream.h>
const int BIG =3D 10000;
short minstamps[10000 * (200 + 3) + 3];
int stamps;
int value[200];
int number;
int=20
main ()
{
ifstream filein ("stamps.in");
filein >> number >> stamps;
int biggest =3D -1;
for (int i =3D 0; i < stamps; ++i) {
filein >> value[i];
if (biggest < value[i]) {
biggest =3D value[i];
}
}
filein.close ();
for (int i =3D 0; i <=3D biggest * number + 3; ++i) {
minstamps[i] =3D BIG;
}
minstamps[0] =3D 0;
for (int i =3D 0; i < stamps; ++i) {
for (int j =3D 0; j <=3D biggest * number; ++j) {
if (minstamps[j] < number) {
if (minstamps[j + value[i]] > 1 + minstamps[j]) {
minstamps[j + value[i]] =3D 1 + minstamps[j];
}
}
}
}
int string =3D 0;
while (minstamps[string + 1] <=3D number) {
++string;
}
ofstream fileout ("stamps.out");
fileout << string << endl;
fileout.close ();
return (0);
}</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
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/b5895160134537db8cb10dcd.htm=
l#send">=C6=C0=C2=DB</A> (0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'USACO 3.1.5 Contact =CC=E2=BD=E2', 'USACO 3.1.5 =
Contact =
=CC=E2=BD=E2','/leokan/blog/item/92e842c2c41cec31e4dd3b5e.html'];
var post =3D [true,'USACO 3.2.1 Factorials =CC=E2=BD=E2','USACO 3.2.1 =
Factorials =CC=E2=BD=E2', =
'/leokan/blog/item/b7b1666324db02640d33fad8.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>');
}
/*]]>*/
</SCRIPT>
</DIV>
<DIV class=3Dline></DIV>
<STYLE type=3Dtext/css>#in_related_doc A {
TEXT-DECORATION: none
}
</STYLE>
<DIV id=3Din_related_tmp></DIV>
<SCRIPT language=3Djavascript type=3Dtext/javascript>
/*<![CDATA[*/
function HI_MOD_IN_RELATED_DOC_CALLBACK(arg){
if(arg.length <=3D 1) return false;
var hasMore =3D arg[0];
var D=3Dfunction(A,B){A[A.length]=3DB;}
if(arg.length % 2 =3D=3D 0) D(arg, ["","","",""]);
var html =3D ['<div id=3D"in_related_doc"><div =
class=3D"tit">=CF=E0=B9=D8=CE=C4=D5=C2=A3=BA</div>'];
D(html, '<table cellpadding=3D"0" cellspacing=3D"3" border=3D"0">');
for(var i =3D 1, j =3D arg.length; i < j; i +=3D 2){
D(html, '<tr>');
D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>•</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i][3] + =
'/blog/item/' + arg[i][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i][0] + '">' + arg[i][1] + '</a>');
D(html, new Array(10).join('\u3000'));
D(html, '</td>');
if(arg[i + 1][0] !=3D "")
D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>•</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i + 1][3] + =
'/blog/item/' + arg[i + 1][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i + 1][0] + '">' + arg[i + 1][1] + '</a></td>');
else
D(html, '<td> </td><td> </td>');
D(html, '</tr>');
}
if(hasMore) D(html, '<tr><td colspan=3D"4"><a target=3D"_blank" =
href=3D"/sys/search?pageno=3D1&type=3D7&sort=3D1&word=3DUSACO%203%2E1%2E6=
%20Stamps%20%CC%E2%BD%E2&item=3Db5895160134537db8cb10dcd">=B8=FC=B6=E0>=
;></a></td></tr>');
D(html, '</table></div><div class=3D"line"> </div>');
var div =3D document.getElementById('in_related_tmp');
if(div){
div.innerHTML =3D html.join('');
while(div.firstChild){
div.parentNode.insertBefore(div.firstChild, div);
}
div.parentNode.removeChild(div);
}
}
if(RelatedDocData =3D=3D -1){ // not supported xhr
var script =3D document.createElement('script');
script.type =3D 'text/javascript';
script.src =3D =
'/sys/search?type=3D8&word=3DUSACO%203%2E1%2E6%20Stamps%20%CC%E2%BD%E2&it=
em=3Db5895160134537db8cb10dcd&t=3D' + new Date().getTime();
document.getElementsByTagName('HEAD')[0].appendChild(script);
}else if(RelatedDocData =3D=3D null){
GetAndEval =3D true;
}else{
eval(RelatedDocData);
}
/*]]>*/
</SCRIPT>
<DIV id=3Din_reader>
<DIV class=3Dtit>=D7=EE=BD=FC=B6=C1=D5=DF=A3=BA</DIV>
<SCRIPT>
var g_spAnnony=3Dtrue;
var g_read=3D[
{}
];
g_read.length=3Dg_read.length-1;
var _rh1=3D"";
var _rh2=3D"";
function wrreader(){
_rh1 +=3D '<table width=3D"100%" ><tr>';
_rh2+=3D'<tr>';
if(g_spAnnony){
_rh1+=3D'<td align=3D"center" width=3D"10%" ><img border=3D"0" =
width=3D"55" height=3D"55" =
src=3D"http://img.baidu.com/hi/img/portraitn.jpg"></td>';
_rh2+=3D'<td> </td>';
if(g_read.length>0){
_rh1+=3D'<td align=3D"left" width=3D"12%">';
}else{
_rh1+=3D'<td align=3D"left" width=3D"100%">';
}
_rh1+=3D"<a =
href=3D'http://passport.baidu.com/?login&tpl=3Dsp&tpl_reg=3Dsp&u=3D"+myre=
f+"' =
target=3D'_self'>=B5=C7=C2=BC</a>=BA=F3=A3=AC=C4=FA=BE=CD=B3=F6=CF=D6=D4=DA=
=D5=E2=C0=EF=A1=A3</td>";
_rh2+=3D'<td> </td>'
}
if(g_read.length=3D=3D0){
if(!g_spAnnony){
_rh1+=3D'<td align=3Dleft =
width=3D"100%">=D7=EE=BD=FC=BB=B9=C3=BB=D3=D0=B5=C7=C2=BC=D3=C3=BB=A7=BF=B4=
=B9=FD=D5=E2=C6=AA=CE=C4=D5=C2=A1=AD=A1=AD</td>';
_rh2+=3D'<td> </td>';
}
}else{
for(i=3D0,len=3Dg_read.length;i<len;i++){
_rh1+=3D'<td align=3D"center" valign=3D"bottom" width=3D"10%" =
class=3D"user"><a href=3D"/'+g_read[i][0]+'" target=3D"_blank"><img =
border=3D"0" =
src=3D"http://himg.baidu.com/sys/portraitn/item/'+g_read[i][1]+'.jpg"></a=
></td>';
_rh2+=3D'<td align=3D"center" valign=3D"top" class=3D"user"><a =
href=3D"/'+g_read[i][0]+'" target=3D"_blank">'+g_read[i][2]+'</a></td>';
}
}
_rh1+=3D'<td width=3D"100%"></td></tr>';
_rh2+=3D'<td></td></tr></table>';
document.write(_rh1+_rh2);
}
wrreader();
</SCRIPT>
</DIV>
<DIV class=3Dline></DIV>
<SCRIPT language=3DJavaScript>
allkey=3Dallkey+"142d077b0bb076f40bd18714_b5895160134537db8cb10dcd_";
</SCRIPT>
<DIV id=3Din_comment><A name=3Dcomment></A>
<DIV class=3Dtit>=CD=F8=D3=D1=C6=C0=C2=DB=A3=BA</DIV>
<SCRIPT>
function writecmt(type,id,cmtname,cmturl,portraitId){
var html1=3D"";
if(type=3D=3D1){
html1=3D"<a name=3D'"+id+"' href=3D'"+cmturl+"' target=3D'_blank' =
title=3D'"+cmturl+"'><img border=3D'0' =
src=3D'http://himg.baidu.com/sys/portraitn/item/"+portraitId+".jpg'><br>"=
+cmtname+"</a>";
}else{
if(cmtname=3D=3D"" || cmtname=3D=3D"=C4=E4=C3=FB=CD=F8=D3=D1"){
if(cmturl=3D=3D""){
html1=3D"<a name=3D'"+id+"'>=C4=E4=C3=FB=CD=F8=D3=D1</a>";
}else{
html1=3D"<a name=3D'"+id+"' href=3D'"+cmturl+"' target=3D'_blank' =
title=3D'"+cmturl+"'>"+cmtname+"</a>";
}
}else{
if(cmturl=3D=3D""){
html1=3D"<div class=3D'f14' style=3D'display:inline'>=CD=F8=D3=D1:<a =
name=3D'"+id+"'>"+cmtname+"</a></div>";
}else{
html1=3D"<div class=3D'f14' style=3D'display:inline'>=CD=F8=D3=D1:<a =
name=3D'"+id+"' href=3D'"+cmturl+"' target=3D'_blank' =
title=3D'"+cmturl+"'>"+cmtname+"</a></div>";
}
}
}
document.write(html1);
}
</SCRIPT>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -