题目大意就是有一个整数串，有两个人轮流取，每次可以取走一个前缀或后缀。两人都足够聪明，且都会使自己收益最大。求取完后先手比后手多多少。
每次我看见上面那句就会深感自己的愚笨无知。
所以来推推性质？
1.两人取的和是一定的，所以只要先手收益尽量大就可以了，问题转化为求收益尽量大。
2.对于一个区间(l,r)，确定了先后手关系，因为两人都足够聪明，所以答案是确定的。
3.因为每次都是从前面或后面取，所以不管怎么取，剩下的一定是一段连续的串。
对于这种两人够聪明但我不聪明的问题，就把聪明丢给状态就可以了。
直接设D(L,R)表示先手在当前串为[l,r]时聪明地选的最大收益。
那么怎么转移呢？先手收益就是总和-后手收益，综合不变，就是要后手收益最小。
因为后手在先手取完后转先手，所以状态转移就出来了。
D(i,j)=Sum(i,j)-min( (D(i+1,j),D(i+2,j),……,D(j,j)) , (D(i,j-1),D(i,j-2),……,D(i,i)) , 0 )。
其中前面是本次从左边取一段，中间是本次从右边取一段，后面是本次取完。
这么写起来可以打记忆搜，复杂度是O(n^3)的，也跑得过去了。
看着上面那个式子很想优化一下？
设 f(i,j)=min(D(i,j),D(i+1,j),……,D(j,j)), g(i,j)=min(D(i,j-1),D(i,j-2),……,D(i,i))。
则D(i,j)=min( min( f(i+1,j),g(i,j-1) ) , 0)。
f和g的转移也很好做。
f(i,j) = min ( f(i+1,j) , D(i,j) )，g(i,j) = min ( g(i,j-1) , D(i,j) )。
于是就可以O(n^2)解决辣。
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cstring> #include <queue> #include <complex> #include <stack> #define LL long long int #define dob double #define FILE "10891" using namespace std; const int N = 110; int n,f[N][N],g[N][N],D[N][N],S[N]; inline int gi(){ int x=0,res=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();} while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*res; } int main() { while(n=gi()){ memset(f,0,sizeof(f));memset(g,0,sizeof(g)); for(int i=1;i<=n;++i) S[i]=S[i-1]+(D[i][i]=f[i][i]=g[i][i]=gi()); for(int len=2;len<=n;++len) for(int i=1;i<=n;++i){ int j=i+len-1;if(j>n)break; D[i][j]=S[j]-S[i-1]-min(0,min(f[i+1][j],g[i][j-1])); f[i][j]=min(f[i+1][j],D[i][j]); g[i][j]=min(g[i][j-1],D[i][j]); } printf("%d ",2*D[1][n]-(S[n]-S[0])); } return 0; }