zmeu2

Joculet
Problema se rezolva cu ajutorul programarii dinamice. Se construieste o matrice D[i][j] - diferenta maxima pe care o poate obtine jucatorul aflat la mutare. Recurenta se obtine destul de usor, si anume:
 
D[i][i] = V[i], 1 ≤ i ≤ N
D[i][i + 1] = max(V[i] - V[j], V[j] - V[i], V[i] + V[j]), 1 ≤ i ≤ N - 1
D[i][j] = max(D[i][j], V[i] + V[j] - D[i + 1][j - 1]), 1 ≤ i ≤ j ≤ N, j - i ≥ 2
Solutia se va afla in D[1][N].
Pentru a obtine insa 100 de puncte nu trebuie retinuta intreaga matrice, ci doar ultimele doua-trei diagonale. Complexitate finala O(N2).

This is a classic dynamic programming problem and, like most DP problems, is simple if and only if you "get" the induction piece. Additionally, getting full points required figuring out (or knowing) a nice trick for when you need to calculate the sums of lots of different ranges.
Reading the problem, it seems to be very clearly a DP problem. In particular, the fact that the line of coins is always a continuous subrange of the original line is a big clue, and that we should compute Bessie's optimal strategy on the range [i, j] (inclusive on both sides) in terms of smaller ranges. Suppose that s(i, j) is the sum of c[i], c[i+1], ..., c[j]. Let b(i, j) be the most that Bessie can win if she plays *first* on the subrange [i, j]. Then we see that