## A Game - Usaco Sec 3 problem

Moderator: Board moderators

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

### A Game - Usaco Sec 3 problem

hi,

i'm trying to solve this problem, but i don't understand what is mean by optimal strategy. is this mean player 2 always choose largest number that can be pick?

thanks for ur kind response.

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

### Re: A Game - Usaco Sec 3 problem

b3yours3lf wrote:i'm trying to solve this problem, but i don't understand what is mean by optimal strategy. is this mean player 2 always choose largest number that can be pick?
If I remembered correctly the answer for your question is NO. Player can also choose the smaller number if it will give him/her better result at the end of the game.

Hope it helps

kirya
New poster
Posts: 2
Joined: Thu Apr 01, 2004 12:01 pm
Contact:
This problem can be solved using DP. Let
sum[j] - sum of elements from i-th position till j-th position
f1[j] - first player score on this table
f2[j] - second player score on this table
f2[j]=sum[j]-f1[j].