10891 - Game of Sum

[cpp]
描述：博弈題目，雙方可以數組任何一邊取連續的的幾個數組元素的值的和，但不能同時從兩邊去，可以從一邊一次取到頭 
#include <cstdio>  
#include <cstring>  
#include <cstdlib>  
int n,sum; 
int arr[110]; 
int v[110][110]; 
int min(int x,int y) 
{ 
    return x>y?y:x; 
} 
int dp(int x,int y) 
{ 
    if(v[x][y]>sum) return v[x][y]; 
    int c=0; 
    for(int i=x; i<y; i++) c=min(c,dp(x,i)); 
    for(int i=x+1; i<=y; i++) c=min(c,dp(i,y)); 
    v[x][y]=arr[y]-arr[x-1]-c; 
    return v[x][y]; 
} 
int main() 
{ 
    //freopen("a.txt","r",stdin);  
    while(scanf("%d",&n)!=EOF) 
    { 
        if(!n) break; 
        arr[0]=0; 
        for(int i=1; i<=n; i++) 
        { 
            scanf("%d",&arr[i]); 
            arr[i]+=arr[i-1]; 
        } 
        memset(v,-127,sizeof(v)); 
        sum=v[0][0]; 
        printf("%d\n",2*dp(1,n)-arr[n]); 
    } 
    return 0; 
}