UVa10891 - Game of Sum

解題策略

記憶優化DP，列舉區間

假設輸入的n個元素儲存在x[1]到x[n]

dp(i,j)表示前手從第i個到第j個(包含第i個與第j個)能獲得的最大值，

因為每一次只能從左邊或右邊取至少一個以上，

若前手取第i+1到第j個，後手就是dp(i,i);若前手取第i+2到第j個，後手就是dp(i,i+1)，

以此類推，前手取第j到第j個，後手就是dp(i,j-1);

若前手取第i到第i個，後手就是dp(i+1,j);若前手取第i到第i+1個，後手就是dp(i+2,j)，

以此類推，前手取第i到第j-1個，後手就是dp(j,j);

若前手取第i到第j個，則後手為0。

為了讓前手取得最大，當然就是讓後手的所有可能性要取最小值，總和減去此最小值，就是先手的最大值

若i<j，dp(i,j)等於sum[i..j]-min(dp(i,i),dp(i,i+1),...,dp(i,j-1),dp(i+1,j),dp(i+2,j),...,dp(j,j),0)

否則i==j，d(i,i)為x[i]，因為至少要取一個

範例測資解析

4 -10 -20 7

先手A不能取7，因為後手B可以取4 -10，先手A只能取-20，先手A獲得-13，後手B獲得-6，-13-(-6)=-7

先手A取4，後手B取7，先手A取-10，後手取-20，先手A為-6，後手B為-13，-6-(-13)=7

參考程式碼