📄 usaco 3_3_2 shopping offers 题解_leokan的blog.mht
字号:
special=20
offer consists of one or more product items together for a reduced =
price,=20
also an integer. Examples: <BR><BR>three flowers for 5z instead of =
6z, or=20
<BR>two vases together with one flower for 10z instead of 12z. =
<BR>Write a=20
program that calculates the price a customer has to pay for a =
purchase,=20
making optimal use of the special offers to make the price as low =
as=20
possible. You are not allowed to add items, even if that would =
lower the=20
price. <BR><BR>For the prices and offers given above, the (lowest) =
price=20
for three flowers and two vases is 14z: two vases and one flower =
for the=20
reduced price of 10z and two flowers for the regular price of 4z.=20
<BR><BR>PROGRAM NAME: shopping<BR>INPUT FORMAT<BR>The input file =
has a set=20
of offers followed by a purchase. Line 1: s, the =
number of=20
special offers, (0 <=3D s <=3D 99). <BR>Line=20
2..s+1: Each line describes an offer using several =
integers.=20
The first integer is n (1 <=3D n <=3D 5), the number of =
products that=20
are offered. The subsequent n pairs of integers c and k indicate =
that k=20
items (1 <=3D k <=3D 5) with product code c (1 <=3D c =
<=3D 999) are=20
part of the offer. The last number p on the line stands for the =
reduced=20
price (1 <=3D p <=3D 9999). The reduced price of an offer is =
less than=20
the sum of the regular prices. <BR>Line =
s+2: The=20
first line contains the number b (0 <=3D b <=3D 5) of =
different kinds of=20
products to be purchased. <BR>Line =
s+3..s+b+2: Each=20
of the subsequent b lines contains three values: c, k, and p. The =
value c=20
is the (unique) product code (1 <=3D c <=3D 999). The value =
k indicates=20
how many items of this product are to be purchased (1 <=3D k =
<=3D 5).=20
The value p is the regular price per item (1 <=3D p <=3D =
999). At most=20
5*5=3D25 items can be in the basket. <BR><BR><BR>SAMPLE =
INPUT=20
(file shopping.in) <BR>2<BR>1 7 3 5<BR>2 7 1 8 2 10<BR>2<BR>7 3 =
2<BR>8 2=20
5<BR><BR>OUTPUT FORMAT<BR>A single line with one integer: the =
lowest=20
possible price to be paid for the purchases. <BR>SAMPLE OUTPUT =
(file=20
shopping.out)<BR>14<BR><BR><BR><BR>Shopping=20
Offers<BR><BR>=C9=CC=B5=EA=B9=BA=CE=EF<BR><BR>IOI'95<BR><BR>=D2=EB =
by Felicia=20
=
Crazy<BR><BR>=D4=DA=C9=CC=B5=EA=D6=D0=A3=AC=C3=BF=D2=BB=D6=D6=C9=CC=C6=B7=
=B6=BC=D3=D0=D2=BB=B8=F6=BC=DB=B8=F1=A3=A8=D3=C3=D5=FB=CA=FD=B1=ED=CA=BE=A3=
=A9=A1=A3=C0=FD=C8=E7,=D2=BB=B6=E4=BB=A8=B5=C4=BC=DB=B8=F1=CA=C7 2 =
zorkmids =
=A3=A8z=A3=A9=A3=AC=B6=F8=D2=BB=B8=F6=BB=A8=C6=BF=B5=C4=BC=DB=B8=F1=CA=C7=
=20
5z =
=A1=A3=CE=AA=C1=CB=CE=FC=D2=FD=B8=FC=B6=E0=B5=C4=B9=CB=BF=CD=A3=AC=C9=CC=B5=
=EA=BE=D9=D0=D0=C1=CB=B4=D9=CF=FA=BB=EE=B6=AF=A1=A3 =
<BR><BR>=B4=D9=CF=FA=BB=EE=B6=AF=B0=D1=D2=BB=B8=F6=BB=F2=B6=E0=B8=F6=C9=CC=
=C6=B7=D7=E9=BA=CF=C6=F0=C0=B4=BD=B5=BC=DB=CF=FA=CA=DB=A3=AC=C0=FD=C8=E7=A3=
=BA <BR><BR>=C8=FD=B6=E4=BB=A8=B5=C4=BC=DB=B8=F1=CA=C7=20
5z =B6=F8=B2=BB=CA=C7 6z=A3=AC =
<BR>=C1=BD=B8=F6=BB=A8=C6=BF=BA=CD=D2=BB=B6=E4=BB=A8=B5=C4=BC=DB=B8=F1=CA=
=C7 10z =B6=F8=B2=BB=CA=C7 12z=A1=A3=20
=
<BR>=B1=E0=D0=B4=D2=BB=B8=F6=B3=CC=D0=F2=A3=AC=BC=C6=CB=E3=B9=CB=BF=CD=B9=
=BA=C2=F2=D2=BB=B6=A8=C9=CC=C6=B7=B5=C4=BB=A8=B7=D1=A3=AC=BE=A1=C1=BF=C0=FB=
=D3=C3=D3=C5=BB=DD=CA=B9=BB=A8=B7=D1=D7=EE=C9=D9=A1=A3=BE=A1=B9=DC=D3=D0=CA=
=B1=BA=F2=CC=ED=BC=D3=C6=E4=CB=FB=C9=CC=C6=B7=BF=C9=D2=D4=BB=F1=B5=C3=B8=FC=
=C9=D9=B5=C4=BB=A8=B7=D1=A3=AC=B5=AB=CA=C7=C4=E3=B2=BB=C4=DC=D5=E2=C3=B4=D7=
=F6=A1=A3=20
=
<BR><BR>=B6=D4=D3=DA=C9=CF=C3=E6=B5=C4=C9=CC=C6=B7=D0=C5=CF=A2=A3=AC=B9=BA=
=C2=F2=C8=FD=B6=E4=BB=A8=BA=CD=C1=BD=B8=F6=BB=A8=C6=BF=B5=C4=D7=EE=C9=D9=BB=
=A8=B7=D1=CA=C7=A3=BA=D2=D4=D3=C5=BB=DD=BC=DB=B9=BA=C2=F2=C1=BD=B8=F6=BB=A8=
=C6=BF=BA=CD=D2=BB=B6=E4=BB=A8=A3=A810z=A3=A9=A3=AC=D2=D4=D4=AD=BC=DB=B9=BA=
=C2=F2=C1=BD=B6=E4=BB=A8=A3=A84z=A3=A9=A1=A3=20
<BR><BR>PROGRAM NAME: shopping<BR>INPUT=20
=
FORMAT<BR>=CA=E4=C8=EB=CE=C4=BC=FE=B0=FC=C0=A8=D2=BB=D0=A9=C9=CC=B5=EA=CC=
=E1=B9=A9=B5=C4=D3=C5=BB=DD=D0=C5=CF=A2=A3=AC=BD=D3=D7=C5=CA=C7=B9=BA=CE=EF=
=C7=E5=B5=A5=A1=A3 <BR><BR>=B5=DA=D2=BB=D0=D0 =
=D3=C5=BB=DD=C9=CC=C6=B7=B5=C4=D6=D6=C0=E0=CA=FD=A3=A80 <=3D s =
<=3D=20
99=A3=A9=A1=A3 <BR>=B5=DA=B6=FE=D0=D0..=B5=DAs+1 =D0=D0 =
=C3=BF=D2=BB=D0=D0=B6=BC=D3=C3=BC=B8=B8=F6=D5=FB=CA=FD=C0=B4=B1=ED=CA=BE=D2=
=BB=D6=D6=D3=C5=BB=DD=B7=BD=CA=BD=A1=A3=B5=DA=D2=BB=B8=F6=D5=FB=CA=FD n =
=A3=A81 <=3D n <=3D=20
=
5=A3=A9=A3=AC=B1=ED=CA=BE=D5=E2=D6=D6=D3=C5=BB=DD=B7=BD=CA=BD=D3=C9 n =
=D6=D6=C9=CC=C6=B7=D7=E9=B3=C9=A1=A3=BA=F3=C3=E6 n =B6=D4=D5=FB=CA=FD c =
=BA=CD k =B1=ED=CA=BE k =A3=A81 <=3D k <=3D =
5=A3=A9=B8=F6=B1=E0=BA=C5=CE=AA c =A3=A81=20
<=3D c <=3D =
999=A3=A9=B5=C4=C9=CC=C6=B7=B9=B2=CD=AC=B9=B9=B3=C9=D5=E2=D6=D6=D3=C5=BB=DD=
=A3=AC=D7=EE=BA=F3=B5=C4=D5=FB=CA=FD p =
=B1=ED=CA=BE=D5=E2=D6=D6=D3=C5=BB=DD=B5=C4=D3=C5=BB=DD=BC=DB=A3=A81 =
<=3D p <=3D=20
=
9999=A3=A9=A1=A3=D3=C5=BB=DD=BC=DB=D7=DC=CA=C7=B1=C8=D4=AD=BC=DB=B5=CD=A1=
=A3 <BR>=B5=DA s+2 =D0=D0 =
=D5=E2=D2=BB=D0=D0=D3=D0=D2=BB=B8=F6=D5=FB=CA=FD b =A3=A80 <=3D b =
<=3D=20
5=A3=A9=A3=AC=B1=ED=CA=BE=D0=E8=D2=AA=B9=BA=C2=F2 b =
=D6=D6=B2=BB=CD=AC=B5=C4=C9=CC=C6=B7=A1=A3 <BR>=B5=DA s+3 =D0=D0..=B5=DA =
s+b+2 =D0=D0 =D5=E2 b =
=D0=D0=D6=D0=B5=C4=C3=BF=D2=BB=D0=D0=B0=FC=C0=A8=C8=FD=B8=F6=D5=FB=CA=FD=A3=
=BAc=20
=A3=ACk =A3=AC=BA=CD p =A1=A3c =
=B1=ED=CA=BE=CE=A8=D2=BB=B5=C4=C9=CC=C6=B7=B1=E0=BA=C5=A3=A81 <=3D c =
<=3D 999=A3=A9=A3=ACk =B1=ED=CA=BE=D0=E8=D2=AA=B9=BA=C2=F2=B5=C4 c =
=C9=CC=C6=B7=B5=C4=CA=FD=C1=BF=A3=A81 <=3D k=20
<=3D 5=A3=A9=A1=A3p =B1=ED=CA=BE c =
=C9=CC=C6=B7=B5=C4=D4=AD=BC=DB=A3=A81 <=3D p <=3D =
999=A3=A9=A1=A3=D7=EE=B6=E0=B9=BA=C2=F2 5*5=3D25 =
=B8=F6=C9=CC=C6=B7=A1=A3 <BR><BR>SAMPLE=20
INPUT (file shopping.in) <BR>2<BR>1 7 3 5<BR>2 7 1 8 2 =
10<BR>2<BR>7 3=20
2<BR>8 2 5<BR>OUTPUT =
FORMAT<BR>=D6=BB=D3=D0=D2=BB=D0=D0=A3=AC=CA=E4=B3=F6=D2=BB=B8=F6=D5=FB=CA=
=FD=A3=BA=B9=BA=C2=F2=D5=E2=D0=A9=CE=EF=C6=B7=B5=C4=D7=EE=B5=CD=BC=DB=B8=F1=
=A1=A3 <BR><BR>SAMPLE=20
OUTPUT (file shopping.out)<BR>14</DIV>
<HR>
<P><STRONG>USACO 3.3.2 Shopping =
Offers<BR>=CC=E1=BD=BB=B4=CE=CA=FD:1=B4=CE</STRONG></P>
=
<P><STRONG>=BC=F2=B5=A5=B5=C4DP,=BA=CD=B1=B3=B0=FC=B2=EE=B2=BB=B6=E0,=D3=C9=
1=CE=AC=BD=F8=B5=BD5=CE=AC</STRONG></P>
<P><STRONG>{<BR>TASK:shopping<BR>LANG:PASCAL<BR>}<BR>program=20
shopping;<BR>var<BR> index:array[1..999] of=20
integer;<BR> cheapness:array[1..104,0..5] of=20
integer;<BR> value:array[1..104] of=20
integer;<BR> need:array[1..5] of=20
integer;<BR> former:array[1..5] of=20
integer;<BR> s,b:integer;<BR>procedure=20
init;<BR>var<BR> =
i,j,x:integer;<BR> =20
pass:string;<BR>begin<BR> =20
assign(input,'shopping.in');reset(input);<BR> =20
readln(s);<BR> for i:=3D1 to s=20
do<BR> =20
readln(pass);<BR> =
readln(b);<BR> for=20
i:=3D1 to b do<BR> =20
=
begin<BR> &nbs=
p;=20
=
read(x);<BR> &=
nbsp;=20
=
index[x]:=3Di;<BR> &=
nbsp; =20
=
read(need[i]);<BR> &=
nbsp; =20
readln(former[i]);<BR> =20
end;<BR> close(input);<BR> =20
assign(input,'shopping.in');reset(input);<BR> =20
readln(s);<BR> for i:=3D1 to s=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
read(cheapness[i,0]);<BR> =
=20
for j:=3D1 to cheapness[i,0]=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p; =20
=
read(x);<BR> &=
nbsp; =20
=
read(cheapness[i,index[x]]);<BR>  =
; =20
=
end;<BR>  =
;=20
readln(value[i]);<BR> =20
end;<BR> for i:=3Ds+1 to s+b=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
cheapness[i,i-s]:=3D1;<BR>  =
; =20
=
value[i]:=3Dformer[i-s];<BR> =20
end;<BR>end;<BR>function=20
min(x,y:integer):integer;<BR>begin<BR> if =
x>=3Dy then=20
exit(y)<BR> else exit(x);<BR>end;<BR>procedure=20
dp;<BR>var<BR> f:array[0..5,0..5,0..5,0..5,0..5] =
of=20
longint;<BR> =20
i,i1,i2,i3,i4,i5,j,k:integer;<BR>begin<BR> for =
i1:=3D0 to=20
need[1] do<BR> for =
i2:=3D0 to=20
need[2]=20
=
do<BR> =
for i3:=3D0 to need[3]=20
=
do<BR> &=
nbsp; =20
for i4:=3D0 to need[4]=20
=
do<BR> &=
nbsp; =20
for i5:=3D0 to need[5]=20
=
do<BR> &=
nbsp; =20
f[i1,i2,i3,i4,i5]:=3Dmaxlongint;<BR> =20
f[0,0,0,0,0]:=3D0;<BR> for i1:=3D0 to need[1]=20
do<BR> for i2:=3D0 to =
need[2]=20
=
do<BR> =
for i3:=3D0 to need[3]=20
=
do<BR> &=
nbsp; =20
for i4:=3D0 to need[4]=20
=
do<BR> &=
nbsp; =20
for i5:=3D0 to need[5]=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p;  =
; =20
for i:=3D1 to s+b=20
=
do<BR> &=
nbsp; &n=
bsp; =20
if=20
=
(i1-cheapness[i,1]>=3D0)and(i2-cheapness[i,2]>=3D0)and(i3-cheapness=
[i,3]>=3D0)and(i4-cheapness[i,4]>=3D0)and(i5-cheapness[i,5]>=3D0=
)=20
=
then<BR>  =
; =
=
if=20
=
f[i1-cheapness[i,1],i2-cheapness[i,2],i3-cheapness[i,3],i4-cheapness[i,4]=
,i5-cheapness[i,5]]+value[i]<f[i1,i2,i3,i4,i5]=20
=
then<BR>  =
; =
&=
nbsp; =20
=
f[i1,i2,i3,i4,i5]:=3Df[i1-cheapness[i,1],i2-cheapness[i,2],i3-cheapness[i=
,3],i4-cheapness[i,4],i5-cheapness[i,5]]+value[i];<BR> &=
nbsp; &n=
bsp; =20
end;<BR> =20
=
assign(output,'shopping.out');rewrite(output);<BR> =20
=
writeln(f[need[1],need[2],need[3],need[4],need[5]]);<BR>  =
;=20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> dp;<BR>end.</STRONG></P><STRONG>
<HR>
</STRONG>
=
<P><STRONG>USACO=B5=C4=B7=D6=CE=F6,=C7=B0=D2=BB=B8=F6=CA=C7=BB=AF=CE=AA=CD=
=BC=C2=DB...=D3=D0=C7=B0=CD=BE</STRONG></P>
<P><STRONG>This is a shortest path problem. The goal is to find =
the=20
shortest path from an empty basket to a basket containing the =
requested=20
objects. Thus, Dijkstra's algorithm can be used. </STRONG></P>
<P><STRONG>The nodes in the graph correspond to baskets and the =
edges=20
correspond to offers (purchasing a single item can be considered a =
degenerate offer). The length of an edge is the cost of the offer. =
For=20
each item type, there can be between 0 and 5 inclusive objects of =
that=20
type in the basket, for a total of 6<SUP>5</SUP> =3D 7,776 =
possible baskets.=20
</STRONG></P><PRE><STRONG>#include <stdio.h>
#include <string.h>
/* maximum number of offers */
/* 100 offers + 5 degenerate offers */
#define MAXO 105
typedef struct OFFER_T
{
int nitem; /* number of items in the offer */
int itemid[5]; /* item's id */
int itemamt[5]; /* item's amount */
int cost; /* the cost of this offer */
} offer_t;
offer_t offers[MAXO];
int noffer;
/* the cost of each basket type */
int cost[7776];
/* the item statistics */
int itemid[5]; /* the id */
int itemcst[5]; /* the cost of buying just 1 */
int nitem;
/* heap used by Dijkstra's algorithm */
int heap[7776];
int hsize;
int hloc[7776]; /* location of baskets within the heap */
/* debugging routine */
void check_heap(void)
{ /* ensure heap order is maintained */
int lv;
return;
for (lv =3D 1; lv < hsize; lv++)
{
if (cost[heap[lv]] < cost[heap[(lv-1)/2]])
{
fprintf (stderr, "HEAP ERROR!\n");
return;
}
}
}
/* delete the minimum element in the heap */
void delete_min(void)
{
int loc, val;
int p, t;
/* take last item from the heap */
loc =3D heap[--hsize];
val =3D cost[loc];
/* p is the current position of item (loc,val) in the heap */
/* the item isn't actually there, but that's where we're
considering putting it */
p =3D 0;=20
while (2*p+1 < hsize)
{ /* while one child is less than the last item,
move the lesser child up */
t =3D 2*p+1;
/* pick lesser child */
if (t+1 < hsize && cost[heap[t+1]] < cost[heap[t]]) =
t++;
if (cost[heap[t]] < val)
{ /* if child is less than last item, move it up */
heap[p] =3D heap[t];
hloc[heap[p]] =3D p;
p =3D t;
} else break;
}
/* put the last item back into the heap */
heap[p] =3D loc;
hloc[loc] =3D p;
check_heap();
}
/* we decreased the value corresponding to basket loc */
/* alter heap to maintain heap order */
void update(int loc)
{
int val;
int p, t;
val =3D cost[loc];
p =3D hloc[loc];
while (p > 0) /* while it's not at the root */
{
t =3D (p-1)/2; /* t =3D parent of node */
if (cost[heap[t]] > val)
{ /* parent is higher cost than us, swap */
heap[p] =3D heap[t];
hloc[heap[p]] =3D p;
p =3D t;
} else break;
}
/* put basket back into heap */
heap[p] =3D loc;
hloc[loc] =3D p;
check_heap();
}
/* add this element into the heap */
void add_heap(int loc)
{
if (hloc[loc] =3D=3D -1)
{ /* if it's not in the heap */
/* add it to the end (same as provisionally setting it's value
to infinity) */
heap[hsize++] =3D loc;
hloc[loc] =3D hsize-1;
}
/* set to correct value */
update(loc);
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -