传送门
思路：区间 d p dp dp。想了好半天+看题解才搞明白，这里再梳理一遍。
显然当 A A A的取值和最大时，因为 s u m A + s u m B = sum_A+sum_B= sumA+sumB=常数，所以 s u m A − s u m B sum_A-sum_B sumA−sumB最大。
令 d p [ l ] [ r ] dp[l][r] dp[l][r]为区间 [ l , r ] , A 和 B [l,r],A和B [l,r],A和B的最大差值。
因为 d p [ 1 ] [ n ] = s u m A − s u m B dp[1][n]=sum_A-sum_B dp[1][n]=sumA−sumB。
所以 s u m A = ( d p [ 1 ] [ n ] + p r e [ n ] ) 2 sum_A=\dfrac{(dp[1][n]+pre[n])}{2} sumA=2(dp[1][n]+pre[n])
当先手取左区间 [ l , l ′ − 1 ] [l,l'-1] [l,l′−1],剩余区间为 [ l ′ , r ] [l',r] [l′,r], l ′ ∈ [ l + 1 , r ] l'\in[l+1,r] l′∈[l+1,r]时有转移方程：
d p [ l ] [ r ] = m a x ( d p [ l ] [ r ] , p r e [ l ′ − 1 ] − p r e [ l − 1 ] − d p [ l ′ ] [ r ] ) dp[l][r]=max(dp[l][r],pre[l'-1]-pre[l-1]-dp[l'][r]) dp[l][r]=max(dp[l][r],pre[l′−1]−pre[l−1]−dp[l′][r])。
表示的是先手只能取得左区间的数 [ l , l ′ − 1 ] [l,l'-1] [l,l′−1]和后面的状态(之前的后手变为先手的最大差值 d p [ l ′ ] [ r ] dp[l'][r] dp[l′][r])。
右区间同理,剩余区间为 [ l , r ′ ] [l,r'] [l,r′]：
d p [ l ] [ r ] = a m x ( d p [ l ] [ r ] , p r e [ r ] − p r e [ r ′ ] − d p [ l ] [ r ′ ] ) dp[l][r]=amx(dp[l][r],pre[r]-pre[r']-dp[l][r']) dp[l][r]=amx(dp[l][r],pre[r]−pre[r′]−dp[l][r′]).
因为这样是 O ( n 3 ) O(n^3) O(n3)的，所以考虑优化。
显然我们可以预处理左区间计算时的 p r e [ l ′ − 1 ] − d p [ l ′ ] [ r ] pre[l'-1]-dp[l'][r] pre[l′−1]−dp[l′][r]的最大值和右区间的 p r e [ r ′ ] + d p [ l ] [ r ′ ] pre[r']+dp[l][r'] pre[r′]+dp[l][r′]的最小值。
m x [ l ] [ r ] = m a x ( p r e [ k − 1 ] − d p [ k ] [ r ] ) , k ∈ [ l + 1 , r ] . mx[l][r]=max(pre[k-1]-dp[k][r]),k\in[l+1,r]. mx[l][r]=max(pre[k−1]−dp[k][r]),k∈[l+1,r].
m n [ l ] [ r ] = m i n ( p r e [ k ] + d p [ l ] [ k ] ) , k ∈ [ l , r − 1 ] . mn[l][r]=min(pre[k]+dp[l][k]),k\in[l,r-1]. mn[l][r]=min(pre[k]+dp[l][k]),k∈[l,r−1].
然后对这两个进行区间更新维护即可。
时间复杂度: O ( n 2 ) O(n^2) O(n2)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e3+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a) memset(a,0,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second int mx[N][N],mn[N][N],f[N][N],pre[N],a[N]; //mx[i][j] pre[k-1]-f[k][j] k 属于[i+1,j] //mn[i][j] pre[k]+f[i][k] k属于[i,j-1] int main(){ int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); for(int i=0;i<=n+1;i++){ pre[i]=0; for(int j=1;j<=n+1;j++) f[i][j]=mx[i][j]=mn[i][j]=0; } for(int i=1;i<=n;i++) scanf("%d",&a[i]),pre[i]=pre[i-1]+a[i]; for(int i=1;i<=n;i++){ f[i][i]=a[i],mx[i][i]=pre[i-1]-f[i][i]; mn[i][i]=pre[i]+f[i][i]; } for(int k=2;k<=n;k++) for(int l=1,r=k;r<=n;l++,r++){ f[l][r]=pre[r]-pre[l-1]; f[l][r]=max(f[l][r],mx[l+1][r]-pre[l-1]); f[l][r]=max(f[l][r],pre[r]-mn[l][r-1]); mx[l][r]=max(mx[l+1][r],pre[l-1]-f[l][r]); mn[l][r]=min(mn[l][r-1],pre[r]+f[l][r]); } printf("%d\n",(f[1][n]+pre[n])/2); } return 0; }思路2：参考另一位大佬的，我觉得比上面一种方法好，但是容易超时，自己手写 m i n min min能快一倍的速度。。。
传送门
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e3+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a) memset(a,0,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second int a[N],dp[N][N],f[N][N],g[N][N]; inline void read(int &x){ x=0;int w=1; char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();} for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch&15); x*=w; } int main(){ int t; read(t); while(t--){ int n; read(n); for(reg int i=1;i<=n;i++){ read(a[i]),dp[i][i]=f[i][i]=g[i][i]=a[i]; a[i]+=a[i-1]; } for(reg int k=2;k<=n;k++) for(reg int l=1,r=k;r<=n;l++,r++){ int tmp=0; if(f[l+1][r]<g[l][r-1]) tmp=f[l+1][r]; else tmp=g[l][r-1]; if(tmp>0) tmp=0; dp[l][r]=a[r]-a[l-1]-tmp; if(f[l+1][r]>dp[l][r]) f[l][r]=dp[l][r]; else f[l][r]=f[l+1][r]; if(g[l][r-1]>dp[l][r]) g[l][r]=dp[l][r]; else g[l][r]=g[l][r-1]; } printf("%d\n",dp[1][n]); } return 0; }