📄 usaco 3_3_5 a game 题解_leokan的blog.mht
字号:
<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></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 3.3.5 A Game =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA02=D4=C210=C8=D5 =D0=C7=C6=DA=C8=D5 =
08:23</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 3.3.5 A Game</H2>
<DIV class=3Dt_msgfont>A Game<BR>IOI'96 - Day 1 <BR>Consider the =
following=20
two-player game played with a sequence of N positive integers (2 =
<=3D N=20
<=3D 100) laid onto a game board. Player 1 starts the game. The =
players=20
move alternately by selecting a number from either the left or the =
right=20
end of the sequence. That number is then deleted from the board, =
and its=20
value is added to the score of the player who selected it. A =
player wins=20
if his sum is greater than his opponents. <BR><BR>Write a program =
that=20
implements the optimal strategy. The optimal strategy yields =
maximum=20
points when playing against the "best possible" opponent. Your =
program=20
must further implement an optimal strategy for player 2. =
<BR><BR>PROGRAM=20
NAME: game1<BR>INPUT FORMAT<BR>Line 1: N, the size of =
the=20
board <BR>Line 2-etc: N integers in the =
range=20
(1..200) that are the contents of the game board, from left to =
right=20
<BR><BR>SAMPLE INPUT (file game1.in) <BR>6<BR>4 7 2 9<BR>5 =
2<BR><BR>OUTPUT=20
FORMAT<BR>Two space-separated integers on a line: the score of =
Player 1=20
followed by the score of Player 2. <BR>SAMPLE OUTPUT (file=20
game1.out)<BR>18 11<BR><BR><BR><BR>A =
Game<BR><BR>=D3=CE=CF=B7<BR><BR>IOI'96 -=20
Day<BR><BR>=D2=EB by =
=E5=D0=D2=A3<BR><BR>=D3=D0=C8=E7=CF=C2=D2=BB=B8=F6=CB=AB=C8=CB=D3=CE=CF=B7=
:N(2 <=3D N <=3D=20
=
100)=B8=F6=D5=FD=D5=FB=CA=FD=B5=C4=D0=F2=C1=D0=B7=C5=D4=DA=D2=BB=B8=F6=D3=
=CE=CF=B7=C6=BD=CC=A8=C9=CF=A3=AC=C1=BD=C8=CB=C2=D6=C1=F7=B4=D3=D0=F2=C1=D0=
=B5=C4=C1=BD=B6=CB=C8=A1=CA=FD=A3=AC=C8=A1=CA=FD=BA=F3=B8=C3=CA=FD=D7=D6=B1=
=BB=C8=A5=B5=F4=B2=A2=C0=DB=BC=D3=B5=BD=B1=BE=CD=E6=BC=D2=B5=C4=B5=C3=B7=D6=
=D6=D0=A3=AC=B5=B1=CA=FD=C8=A1=BE=A1=CA=B1=A3=AC=D3=CE=CF=B7=BD=E1=CA=F8=A1=
=A3=D2=D4=D7=EE=D6=D5=B5=C3=B7=D6=B6=E0=D5=DF=CE=AA=CA=A4=A1=A3=20
=
<BR><BR>=B1=E0=D2=BB=B8=F6=D6=B4=D0=D0=D7=EE=D3=C5=B2=DF=C2=D4=B5=C4=B3=CC=
=D0=F2=A3=AC=D7=EE=D3=C5=B2=DF=C2=D4=BE=CD=CA=C7=CA=B9=D7=D4=BC=BA=C4=DC=B5=
=C3=B5=BD=D4=DA=B5=B1=C7=B0=C7=E9=BF=F6=CF=C2=D7=EE=B4=F3=B5=C4=BF=C9=C4=DC=
=B5=C4=D7=DC=B7=D6=B5=C4=B2=DF=C2=D4=A1=A3=C4=E3=B5=C4=B3=CC=D0=F2=D2=AA=CA=
=BC=D6=D5=CE=AA=B5=DA=B6=FE=CE=BB=CD=E6=BC=D2=D6=B4=D0=D0=D7=EE=D3=C5=B2=DF=
=C2=D4=A1=A3<BR><BR>PROGRAM=20
NAME: game1<BR>INPUT FORMAT<BR>=B5=DA=D2=BB=D0=D0: =
=D5=FD=D5=FB=CA=FDN,=20
=
=B1=ED=CA=BE=D0=F2=C1=D0=D6=D0=D5=FD=D5=FB=CA=FD=B5=C4=B8=F6=CA=FD=A1=A3&=
nbsp; <BR>=B5=DA=B6=FE=D0=D0=D6=C1=C4=A9=CE=B2: =
=D3=C3=BF=D5=B8=F1=B7=D6=B8=F4=B5=C4N=B8=F6=D5=FD=D5=FB=CA=FD=A3=A8=B4=F3=
=D0=A1=CE=AA1-200=A3=A9=A1=A3 <BR><BR>SAMPLE=20
INPUT (file game1.in) <BR>6 <BR>4 7 2 9<BR>5 2<BR><BR>OUTPUT=20
=
FORMAT<BR><BR>=D6=BB=D3=D0=D2=BB=D0=D0=A3=AC=D3=C3=BF=D5=B8=F1=B7=D6=B8=F4=
=B5=C4=C1=BD=B8=F6=D5=FB=CA=FD: =
=D2=C0=B4=CE=CE=AA=CD=E6=BC=D2=D2=BB=BA=CD=CD=E6=BC=D2=B6=FE=D7=EE=D6=D5=B5=
=C4=B5=C3=B7=D6=A1=A3 <BR><BR>SAMPLE OUTPUT=20
(file game1.out)<BR>18 11</DIV>
<HR>
<P><STRONG>USACO 3.3.5 A =
Game<BR>=CC=E1=BD=BB=B4=CE=CA=FD:2=B4=CE</STRONG></P>
=
<P><STRONG>=D3=C3DP=D7=F6,f[i,j]=3Dmax{sum[i+1,j]+queue[i]-f[i+1,j],sum[i=
,j-1]+queue[j]-f[i,j-1]}<BR>=B5=DA=D2=BB=B4=CE=CC=E1=BD=BB=CB=B3=D0=F2=B7=
=B4=C1=CB,=B5=F7=D3=C3=C1=CB=D2=BB=D0=A9=BB=B9=CE=B4=B8=B3=D6=B5=B5=C4=B5=
=E3,=CB=AD=D6=AA=BE=B9=C8=BB=B9=FD=C1=CB=BC=B8=B8=F6=B5=E3.</STRONG></P>
<P><STRONG>USACO 3.3.5 A Game =
=BD=E2=CC=E2=B1=A8=B8=E6</STRONG></P>
=
<P><STRONG>=CE=CA=CC=E2=C3=E8=CA=F6:<BR>=B8=F8=B3=F6=D2=BB=B8=F6=D3=D0n=B8=
=F6=CA=FD=D0=F2=C1=D0Q1,Q2,Q3...Qn,=D7=F6=D2=BB=B8=F6=B2=A9=DE=C4=CE=CA=CC=
=E2.<BR>=C1=BD=C8=CB=C2=D6=C1=F7=D6=D8=D0=F2=C1=D0=B5=C4=C1=BD=B6=CB=C8=A1=
=D7=DF=D2=BB=B8=F6=CA=FD,=D4=DA=B5=DA=B6=FE=B8=F6=C8=CB=D2=D4=D7=EE=BC=D1=
=B2=DF=C2=D4=C8=A1=CA=FD=B5=C4=C7=E9=BF=F6=CF=C2=C7=F3=B5=DA=D2=BB=B8=F6=C8=
=CB=C8=A1=CA=FD=B5=C4=BA=CD=B5=C4=D7=EE=B4=F3=D6=B5.</STRONG></P>
=
<P><STRONG>=CE=CA=CC=E2=B7=D6=CE=F6:<BR>=C1=BD=B8=F6=C8=CB=B6=BC=D2=D4=D7=
=EE=BC=D1=B2=DF=C2=D4=C8=A1=CA=FD,=C4=C7=C3=B4=D5=E2=B8=F6=D7=EE=BC=D1=B2=
=DF=C2=D4=BE=CD=CA=C7=D2=BB=B8=F6=D2=BB=B8=F6=D7=EE=D3=C5=BD=E2,=BF=BC=C2=
=C7=D3=D0n-2=B8=F6=CA=FD=B5=C4=D0=F2=C1=D0,=CB=FC=B5=C4=D7=EE=D3=C5=BD=E2=
=CE=AAx,=B8=F8=D5=E2=B8=F6=D0=F2=C1=D0=D4=D9=BC=D3=C9=CF2=B8=F6=CA=FD,Qn-=
1,Qn,=C8=A1=D5=E2=C1=BD=B8=F6=CA=FD=B5=C4=BD=CF=B4=F3=D5=DF=BC=D3=C9=CFx,=
=BE=CD=CA=C7=D2=BB=B8=F6=D0=C2=B5=C4=D7=EE=D3=C5=BD=E2.=B7=B4=B9=FD=C0=B4=
=CB=B5,=C3=BF=B8=F6=D7=EE=D3=C5=BD=E2,=CB=FC=BC=F5=C8=A5=D0=F2=C1=D0=D6=D0=
=B5=C4=D2=BB=B8=F6=CA=FD,=B6=BC=CA=C7=C1=ED=D2=BB=D6=D6=C7=E9=BF=F6=B5=C4=
=D7=EE=D3=C5=BD=E2,=CB=F9=D2=D4=D7=EE=D3=C5=D7=D3=BD=E1=B9=B9=B5=C3=D6=A4=
.<BR>=D2=BB=B8=F6=D7=EE=D3=C5=BD=E2=BF=C9=D2=D4=BC=D3=C9=CF=CA=FD=B1=E4=B3=
=C9=D0=C2=B5=C4=D7=EE=D3=C5=BD=E2,=CB=F9=D2=D4=D6=D8=B5=FE=D7=D3=CE=CA=CC=
=E2=B5=C3=D6=A4.=BF=C9=D2=D4=D3=C3=B6=AF=CC=AC=B9=E6=BB=AE=C7=F3=BD=E2.</=
STRONG></P>
=
<P><STRONG>=B7=FB=BA=C5=BC=B0=B1=E4=C1=BF=CB=B5=C3=F7:<BR>=BC=C7Q=CE=AA=CA=
=FD=B5=C4=D0=F2=C1=D0,Qi=CE=AA=D0=F2=C1=D0=D6=D0=B5=DAi=B8=F6=CA=FD.<BR>=BC=
=C7sum(i,j)=CE=AA=D0=F2=C1=D0=D6=D0=B5=DAi=B8=F6=CA=FD=B5=BD=B5=DAj=B8=F6=
=CA=FD=B5=C4=BA=CD.<BR>=BC=C7f(i,j)=CE=AA=D0=F2=C1=D0=D6=D0=D3=C9i=BF=AA=CA=
=BC=B5=BD=B5=DAj=B8=F6=CA=FD=B0=B4=D5=D5=D3=CE=CF=B7=B9=E6=D4=F2=C4=DC=C8=
=A1=B5=C3=B5=BD=B5=C4=D7=EE=B4=F3=D6=B5.</STRONG></P>
=
<P><STRONG>=C4=A3=D0=CD=B5=C4=BD=A8=C1=A2:<BR>=C9=E8=B5=C3=B5=BD=D2=BB=B8=
=F6=D7=D3=D0=F2=C1=D0Qi,Qi+1,Qi+2,...,Qj-2,Qj-1,Qj;<BR>=D3=C9=D3=DA=BA=F3=
=D2=BB=B8=F6=C8=CB=B0=B4=D7=EE=BC=D1=B2=DF=C2=D4=C8=A1=CA=FD,=CB=F9=D2=D4=
=CB=FB=B1=D8=BD=AB=C8=A1=D2=BB=B8=F6=D7=EE=B4=F3=D6=B5f(i+1,j)=BB=F2f(i,j=
-1),=C4=C7=C3=B4=B4=CB=CA=B1=C8=A1=CA=FD=B5=C4=C8=CB=D2=D4=BA=F3=C8=A1=B5=
=C3=B5=C4=CA=FD=BD=AB=CA=C7sum(i+1,j)-f(i+1,j)=BB=F2=CA=C7sum(i,j-1)-f(i,=
j-1),=B4=CB=CA=B1=C8=A1=CA=FD=B5=C4=C8=CB=B0=B4=D7=EE=BC=D1=B2=DF=C2=D4=C8=
=A1=CA=FD,=CB=FB=BB=E1=C8=A1Qi=BB=F2=D5=DFQj=CA=B9=B5=C3sum(i+1,j)-f(i+1,=
j)+Qi=BA=CDsum(i,j-1)-f(i,j-1)+Qj=B6=FE=D5=DF=C4=DC=D3=D0=BD=CF=B4=F3=D6=B5=
.=D5=E2=D1=F9=B4=D3=D3=CE=CF=B7=B5=C4=BD=E1=CA=F8=CF=F2=D3=CE=CF=B7=B5=C4=
=BF=AA=CA=BC=CD=C6,=BF=C9=D2=D4=B5=C3=B5=BD=D7=DC=B5=C4=D7=EE=D3=C5=BD=E2=
.</STRONG></P>
=
<P><STRONG>=C4=A3=D0=CD=B5=C4=C7=F3=BD=E2:<BR>=CF=D4=C8=BB,f(i,i)=3Dsum(i=
,i)=3DQi;=D5=E2=BF=C9=D2=D4=D7=F7=CE=AA=B1=DF=BD=E7=CC=F5=BC=FE.</STRONG>=
</P>
<P><STRONG>for i=A1=FBn-1 downto 1 do<BR>for j=A1=FBi+1 to n=20
do<BR> begin<BR> =20
sum(i,j)=A1=FBsum(i,j-1)+Qj<BR> =20
=
f[i,j]=A1=FBmax{sum(i+1,j)+Qi-f(i+1,j),sum(i,j-1)+Qj-f(i,j-1)}<BR> &=
nbsp; =20
end;</STRONG></P>
<P></P>
<P><STRONG>code:</STRONG></P>
<P><STRONG>{<BR>TASK:game1<BR>LANG:PASCAL<BR>}<BR>program=20
game1;<BR>const<BR> =20
maxn=3D200;<BR>var<BR> queue:array[1..maxn] of=20
integer;<BR> f:array[1..maxn,1..maxn] of=20
integer;<BR> sum:array[1..maxn,1..maxn] of=20
integer;<BR> n:integer;<BR>procedure=20
init;<BR>var<BR> =20
i:integer;<BR>begin<BR> =20
assign(input,'game1.in');reset(input);<BR> =20
readln(n);<BR> for i:=3D1 to n=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
read(queue[i]);<BR> =
=20
=
sum[i,i]:=3Dqueue[i];<BR> =
=20
f[i,i]:=3Dqueue[i];<BR> =20
end;<BR> close(input);<BR>end;<BR>function=20
max(x,y:integer):integer;<BR>begin<BR> if x>y =
then=20
exit(x)<BR> else exit(y);<BR>end;<BR>procedure=20
dp;<BR>var<BR> =20
i,j:integer;<BR>begin<BR> for i:=3Dn-1 downto 1=20
do<BR> for j:=3Di+1 to n =
=
do<BR> =
=
begin<BR> &nbs=
p; =20
=
sum[i,j]:=3Dsum[i,j-1]+queue[j];<BR> &=
nbsp; =20
=
f[i,j]:=3Dmax(sum[i+1,j]+queue[i]-f[i+1,j],sum[i,j-1]+queue[j]-f[i,j-1]);=
<BR> =20
end;<BR> =20
assign(output,'game1.out');rewrite(output);<BR> =20
writeln(f[1,n],' ',sum[1,n]-f[1,n]);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> dp;<BR>end.</STRONG></P>
<P></P><STRONG>
<HR>
</STRONG>
=
<P><STRONG>=BA=CDUSACO=B5=C4=B7=BD=B7=A8=D2=BB=D2=EC=B3=A3=CF=E0=CB=C6</S=
TRONG></P>
<P><STRONG>We use dynamic programming to determine, for every =
possible=20
piece of board that could be left at any point in the game, how =
many=20
points the best strategy gets for the winner, and how many for the =
loser.=20
</STRONG></P>
<P><STRONG>Let us define best[board] to be the highest score we =
can hope=20
to get by going first starting with the given board. </STRONG></P>
<P><STRONG>If we are looking at a board "a ... b", the best number =
of=20
points is the maximum of the following: =
<BR> a +=20
total[... b] - best[... b] <BR> b + =
total[a ...] -=20
best[a ...] <BR></STRONG></P>
<P><STRONG>We use total[board] - best[board] as the best that we =
can hope=20
to do going second starting with the given board. </STRONG></P>
<P><STRONG>If we are looking at the board "a", the best number of =
points=20
is a. </STRONG></P><PRE><STRONG>#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXBOARD 100
int board[MAXBOARD];
/*
* best and total are indexed so that (e.g.) best[i, l] refers
* to the board of length l starting at place i.
*/
int total[MAXBOARD][MAXBOARD];
int best[MAXBOARD][MAXBOARD];
int
max(int a, int b)
{
return a > b ? a : b;
}
void
main(void)
{
FILE *fin, *fout;
int j, l, n;
fin =3D fopen("game1.in", "r");
fout =3D fopen("game1.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
fscanf(fin, "%d", &n);
for(j=3D0; j<n; j++)
fscanf(fin, "%d", &board[j]);
/* calculate subboard totals */
for(j=3D0; j<n; j++)
total[j][0] =3D 0;
for(l=3D1; l<=3Dn; l++)
for(j=3D0; j+l<=3Dn; j++)
total[j][l] =3D board[j] + total[j+1][l-1];
/* calc best for boards of size one */
for(j=3D0; j+1<=3Dn; j++)
best[j][1] =3D board[j];
/* calc best for bigger boards */
for(l=3D2; l<=3Dn; l++)
for(j=3D0; j+l<=3Dn; j++)
best[j][l] =3D max(board[j] + total[j+1][l-1] - =
best[j+1][l-1],
board[j+l-1] + total[j ][l-1] - best[j =
][l-1]);
fprintf(fout, "%d %d\n", best[0][n], total[0][n]-best[0][n]);
=20
exit(0);
}
</STRONG></PRE>
<H3>Another take on game1</H3>
<P><STRONG><EM>Nick Pilkington of South Africa writes:</EM> =
</STRONG></P>
<P><STRONG>You only need O(n) space for the sum not O(n*n). This=20
eliminates extra calculation as it can be computed during input. =
This also=20
means that the board values don't need to be stored at all, =
leading to a=20
much tighter solution: </STRONG></P><PRE><STRONG>#include =
<fstream>
using namespace std;
#define min(a,b) ((a<b)?a:b)
ifstream fin("game1.in");
ofstream fou("game1.out");
int n;
int sum[101];
int best[101][101];
void main()
{
fin >> n;
for(int i =3D 1; i <=3D n; i++) {
fin >> best[i][i];
sum[i] =3D sum[i-1] + best[i][i];
}
=20
for(int i =3D 1; i <=3D n; i++)
for(int j =3D 1; j+i <=3D n; j++)
best[j+i][j] =3D sum[j+i]-sum[j-1] - min(best[j+i-1][j], =
best[j+i][j+1]);
fou << best[n][1] << " " << sum[n] - best[n][1] =
<< endl;
}
</STRONG></PRE>
<H3>More optimizations</H3>
<P><STRONG><EM>Lucian Boca Romania writes:</EM> </STRONG></P>
<P><STRONG>I propose some memory optimizations for "A Game" =
problem.=20
</STRONG></P>
<P><STRONG>The algorithm is the same, I simulate the calculation =
of the=20
matrix <TT><FONT face=3DNSimsun>best[i][l]</FONT></TT> =3D the =
best score wich=20
can be obtained by the first player with the board pieces =
i,i+1,...,i+l-1=20
(a sequence of numbers starting with position i and having the =
length l).=20
I also simulate the calculation of the matrix <TT><FONT=20
face=3DNSimsun>total[i][l]</FONT></TT> =3D the sum of all elements =
in the=20
sequence starting with position i and having the length l. The =
reccurence=20
relation is: </STRONG></P><PRE><STRONG>best[i][l]=3Dtotal[i][l] - =
min( best[i+1][l-1], best[i][l-1] )
</STRONG></PRE>
<P><STRONG>and our goal is to obtain best[1][n] </STRONG></P>
<P><STRONG>The optimizations: </STRONG></P>
<UL>
<LI><STRONG>You don't need to memorize the board. All the =
information=20
about the board is in <TT><FONT =
face=3DNSimsun>total(i,l)</FONT></TT>=20
</STRONG>
<LI><STRONG>You don't need to use a matrix for <TT><FONT=20
face=3DNSimsun>total(i,l)</FONT></TT>. You calculate a vector =
<TT><FONT=20
face=3DNSimsun>t[i]=3Dthe sum of elements 1,2,...,i</FONT></TT>. =
So,=20
<TT><FONT face=3DNSimsun>total(i,l)</FONT></TT> will be =
<TT><FONT=20
face=3DNSimsun>t[i+l-1] - t[i-1]</FONT></TT> </STRONG>
<LI><STRONG>You don't need to use a matrix NxN, since you only =
need the=20
last two columns. So, instead of using <TT><FONT=20
face=3DNSimsun>l</FONT></TT>, we can use <TT><FONT=20
face=3DNSimsun>l%2</FONT></TT> and allocate the matrix <TT><FONT =
face=3DNSimsun>best[NMAX][2];</FONT></TT> the reccurence =
relation becomes=20
<TT><FONT face=3DNSimsun>best[i][l%2]=3Dtotal(i,l) - min(=20
best[i+1][(l-1)%2], best[i][(l-1)%2])</FONT></TT> and our goal =
is to=20
obtain <TT><FONT face=3DNSimsun>best[1][n%2]</FONT></TT>.=20
</STRONG></LI></UL>
<P><STRONG>Here's the code: </STRONG></P><PRE><STRONG>#include =
<stdio.h>
#define NMAX 101
int best[NMAX][2], t[NMAX];
int n;
void=20
readx () {
int i, aux;
freopen ("game1.in", "r", stdin);
scanf ("%d", &n);
for (i =3D 1; i <=3D n; i++) {
scanf ("%d", &aux);
t[i] =3D t[i - 1] + aux;
}
fclose (stdin);
}
inline int=20
min (int x, int y) {
return x > y ? y : x;
}
void=20
solve () {
int i, l;
for (l =3D 1; l <=3D n; l++)
for (i =3D 1; i + l <=3D n + 1; i++)
best[i][l%2] =3D t[i + l - 1] - t[i - 1] - min (best[i + 1][(l - 1) =
% 2],
best[i][(l - 1) % 2]);
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -