題意:經典的取石子游戲是這樣的:有一堆石子，A、B兩個人輪流取，每次取一顆，只能從邊上取，每個石子有相應的價值，A、B兩人都想使得自己的價值最多，兩個人足夠聰明，問最后價值分別是多少
本題則是可以取多顆，但仍然只能從一側取得
分析：狀態轉移方程
best[i][j]=sum[i][j]-min(best[i][j-k],best[i+k][j]， 0);{1<=k=j-i+1}.
使用了記憶化的方法，O（n3），書上說有進一步的優化，不過當前數據下已經很快了（64ms）
代碼：
View Code 1 #include <stdio.h> 2 #include <iostream> 3 #include <string.h> 4 using namespace std; 5 const int MAXN = 100 + 10; 6 #define DEBUG 7 int min(int a, int b){ 8 return a<b?a:b; 9 } 10 int s[MAXN], a[MAXN], d[MAXN][MAXN], vis[MAXN][MAXN], n; 11 int dp(int i, int j){ 12 if(vis[i][j]) return d[i][j]; 13 vis[i][j]=1; 14 int m=0, k; 15 for(k=i+1; k<=j; k++) m=min(m, dp(k, j)); 16 for(k=i; k<j; k++) m=min(m, dp(i, k)); 17 d[i][j]=s[j]-s[i-1]-m;; 18 return d[i][j]; 19 } 20 int main(){ 21 #ifndef DEBUG 22 freopen("in.txt", "r", stdin); 23 #endif 24 while(scanf("%d", &n)!=EOF && n){ 25 s[0]=0; 26 int i; 27 for(i=1; i<=n; i++){ 28 scanf("%d", &a[i]); 29 s[i] = s[i-1] + a[i]; 30 } 31 memset(vis, 0, sizeof(vis)); 32 printf("%d\n", 2*dp(1,n)-s[n]); 33 } 34 return 0; 35 }
?
?
