Min-Max Search

[Dimitar]

Can you help me with this task. I think that it can be
solved with min-max search, but i can't find an example on
how to implement this algorithm.


Game

Two players are playing this game: There are n numbers (n<=128), ordered in a row.
The first player takes one number from the left or the right side.
Then the second player takes one number from the left or the right
side of the rest of the numbers.
In this way they take the numbers, until there are no numbers left. What is
the maximum sum of the numbers that the first player has taken, if the both
players are playing optimal.

input:
first line: n - the number of numbers
second lind: n numbers, of which a <= 100

output:
the maximum sum of numbers that the first player can take

[Zyaad Jaunnoo]

DP problem...

[Dimitar]

OK, thanks

[Quantris]

It's actually way way simpler than DP

think about parity.

[misof]

It's actually way way simpler than DP

think about parity.

Nope. To win or draw this game, "thinking about parity" is enough. But the greedy algorithm doesn't guarantee that you get the maximal sum.

Consider the following input:

Code: Select all

8
3 0 3 0 3 0 3 10

The greedy algorithm will win 12:10, but the first player can force a 19:3 win.

[Quantris]

just do the "parity" technique at each step.

Maybe that is DP after all.

[misof]

just do the "parity" technique at each step.

Maybe that is DP after all.

Would you care to explain your algorithm in more detail, preferably on my input?

[Fixxxer]

Isnt it a usaco problem?
i solved it using memoization

max_profit(i,j)=MAX((a[i]+sum[i+1][j]-max_profit(i+1,j)),(a[j]+sum[i][j-1]-max_profit(i,j-1)))