USACO Contest 2010 Silver

[•APOCALYPTO]

Nu reusesc sa gasesc recurenta buna la problema Treasure.
In concurs amluat 4 teste(din 10) si cand m-am uitat ieri pe sursa mi-am data seama ca recurenta era complet gresita.

Eu in concurs am luat starea
dp[player][ i][j]-valoarea maxima pe care o poate obtine jucatorul player(Bessie este 1, Bonnie este 0) din primele i si ultimele j monede.

Rezultatul a fost maximul elementelor dp[1][ i][N-i] cu i=0 la N


Starile initiale au fost dp[1][0][0]=dp[0][0][0]=0.

Iar relatia mea de recurenta este

  dp[player][ i][j]= suma_stanga[ i]+ suma_dreapta[N-j+1] - min(dp[1-player][ i-1][j] , dp[1-player][ i][j-1] );

cu suma_stanga[ x]=suma primelor x monede;
si suma_dreapta[N-x+1]=suma ultimelor x monede;


Imi poate spune si mie cineva ce este gresit in rationamentul meu?