A Game - Usaco Sec 3 problem

[b3yours3lf]

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]

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]

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].

answer is f1[1][n] and f2[1][n]