有一个长度为n的整数序列，两个游戏者A和B轮流取数，A先取。每次玩家只能从左端或者右端取任意数量的数，但不能两边都取。所有数都被取走视为游戏结束，然后统计每个人取走的数之和，作为各自的得分。两个人采取的策略都是让自己得分尽可能高，并且两个人都很机智，求A得分-B得分后的结果。
输入格式
输入包含多组数据，每组数据第一行为正整数n(1<=n<=100) ，第二行为给定的整数序列，输入结束标志是n=0
输出格式
对于每组数据，输出A和B都采取最优策略下，A的得分-B的得分
不要多想，就是道区间dp水题，前缀和优化一下
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e6+5; 4 const int INF=1e9+5; 5 int n,a[105],d[105][105],f[105][105],g[105][105],sum[105]; 6 template <class t>void red(t &x) 7 { 8 x=0; 9 int w=1; 10 char ch=getchar(); 11 while(ch<'0'||ch>'9') 12 { 13 if(ch=='-') 14 w=-1; 15 ch=getchar(); 16 } 17 while(ch>='0'&&ch<='9') 18 { 19 x=(x<<3)+(x<<1)+ch-'0'; 20 ch=getchar(); 21 } 22 x*=w; 23 } 24 void input() 25 { 26 freopen("input.txt","r",stdin); 27 //freopen("output.txt","w",stdout); 28 } 29 int main() 30 { 31 //input(); 32 while(1) 33 { 34 red(n); 35 if(!n) 36 break; 37 memset(d,0x3f,sizeof(d)); 38 memset(f,0x3f,sizeof(f)); 39 memset(g,0x3f,sizeof(g)); 40 for(int i=1;i<=n;++i) 41 { 42 red(a[i]); 43 f[i][i]=g[i][i]=d[i][i]=a[i]; 44 sum[i]=sum[i-1]+a[i]; 45 } 46 for(int i=2;i<=n;++i) 47 for(int j=1;j+i<=n+1;++j) 48 { 49 int e=j+i-1; 50 d[j][e]=sum[e]-sum[j-1]-min(min(f[j+1][e],g[j][e-1]),0); 51 f[j][e]=min(f[j+1][e],d[j][e]); 52 g[j][e]=min(g[j][e-1],d[j][e]); 53 } 54 printf("%d ",2*d[1][n]-sum[n]); 55 } 56 return 0; 57 }