枚举剩下的序列即可: f(i,j)表示从i到j玩家一取得的最大值,sum[i][j]表示从i到j的和。 f(i,j)=sum[i][j]-min(f(i,k),f(k+1,j),0) i<=j, i<=k<j。
#include <iostream> #include <cstring> using namespace std; int a[105],n,sum[105],bz[105][105],d[105][105]; int solve(int i,int j) { int k,mi=0; if(bz[i][j]) return d[i][j]; bz[i][j]=1; for(k=i;k<j;k++) { mi=min(solve(i,k),mi); mi=min(solve(k+1,j),mi); } return d[i][j]=(sum[j]-sum[i-1])-mi; } int main(int argc, char *argv[]) { int i; while(cin>>n&&n) { for(i=1;i<=n;i++) { cin>>a[i]; sum[i]=sum[i-1]+a[i]; } memset(bz,0,sizeof(bz)); cout<<2*solve(1,n)-(sum[n]-sum[0])<<endl; } return 0; }