题目链接
依据题意可以设计出一个区间 dp。由于先后手操作相同，所以可以只记先手得分的最大值。但是它是 \(\text O (n ^ 3)\) 的。
观察瓶颈转移形如 \(f _ {l, r} \leftarrow - f _ {i, j} + sum (l, r) - sum (i, j) - cost\)，其中区间 \([i, j]\) 长度为定值，可以单调队列优化。
时间复杂度 \(\text O (n ^ 2)\)。
#include<cstdio>
#include<algorithm>
#define N 3005
using namespace std;int n,A,B,C,D,a[N];
int lt,rt;
long long s[N],f[N][N],q[N],w[N];
void work(int m,int k,int c) {lt=1,rt=0;for(int i=k;i<=n;i++) {w[i]=-f[i-k+1][i]-(s[i]-s[i-k]);while(lt<=rt&&w[i]>=w[q[rt]]) rt--;q[++rt]=i;if(i>=m) {if(lt<=rt&&q[lt]<i-m+k) lt++;f[i-m+1][i]=max(f[i-m+1][i],w[q[lt]]+(s[i]-s[i-m])-c);}}
}
int main() {scanf("%d%d%d%d%d",&n,&A,&B,&C,&D);for(int i=1;i<=n;i++) scanf("%d",&a[i]),s[i]=s[i-1]+a[i];for(int len=1;len<=n;len++) {for(int l=1,r=len;r<=n;l++,r++) {f[l][r]=max(-f[l+1][r]+a[l],-f[l][r-1]+a[r]);}work(len,max(len-B,0),A);work(len,max(len-D,0),C);}printf("%lld\n",f[1][n]);return 0;
}