第一眼：区间DP，可以瞎搞

f[i][j]=max(sum(i,j)-f[i+1][j],sum(i,j)-f[i][j-1])

提出来就是f[i][j]=sum(i,j)-min(f[i+1][j],f[i][j-1])

可是空间是64M，就很难受，第二个数据点是极限数据

 

尝试了用部分记忆化的方式找空间时间平衡，但是这样显然是不对的，看起来“省下的空间”实际上成为了更多的栈空间..

 

考虑写一维的DP，既然不可能消一维，就把另一维藏起来。

f[i]表示原来的f[i][i+len]，外层依旧枚举len

f[i]=sum(i,j)-min(f[i],f[i+1])，等号前是要更新的len意义下的f[i][i+len]，后面的f[i]和f[i+1]代表f[i][i+len-1]和f[i+1][i+len]，也就是原来的f[i][j-1]和f[i+1][j]啦

 

是不是只依赖两层的区间DP都可以这样搞呢?类似横向的滚动数组咯？

 想了一下，是不行的。像合并果子、Polygon这种题，虽然也是小区间依赖大区间，外层枚举len，但是有一个枚举断点的操作，导致转移区间长度不具有约束关系

就好比在背包中突然要从历史版本转移，当然是不行的。这种题是转移长度确定的，才能消去一维（类似滚动）。

 

#include
     
      #include
      
       using namespace std;const int MAXN=5050;inline int rd(){  int ret=0,f=1;char c;  while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;  while(isdigit(c))ret=ret*10+c-'0',c=getchar();  return ret*f;}int n;int sum[MAXN];int f[5005];int main(){  n=rd();  int x;  for(int i=1;i<=n;i++) sum[i]=sum[i-1]+(f[i]=rd());  for(int len=1;len<=n;len++){    for(int i=1;i+len<=n;i++){      int j=i+len;      f[i]=sum[j]-sum[i-1]-min(f[i],f[i+1]);    }  }  cout<