经典题，考虑区间 dp，\(f_{l,r}\) 表示只考虑 \([l, r]\) 区间，先手得分减后手得分最大值。
对于第一种操作直接 \(f_{l,r} \gets \max(a_l - f_{l+1,r}, a_r - f_{l,r-1})\)，第二种操作，考虑枚举 \([l,r]\) 长为 \(r - l + 1 - B\) 的子段，即可转移。第三种操作同理。
那么我们得到了一个 \(O(n^3)\) 的做法。考虑优化。发现瓶颈在于枚举子段。发现因为子段长度固定，所以可以直接查固定区间长度的形似 \(f_{p,p+k-1}\) 的最大值。考虑使用 ST 表，按区间长度从小到大计算每个 \(f_{l,r}\)，当一个长度的区间都计算完了，就把它们扔给 ST 表预处理。
时空复杂度均为 \(O(n^2 \log n)\)。
code
// Problem: G - Bags Game
// Contest: AtCoder - NS Solutions Corporation Programming Contest 2023（AtCoder Beginner Contest 303）
// URL: https://atcoder.jp/contests/abc303/tasks/abc303_g
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 3030;
ll n, A, B, C, D, a[maxn], f[maxn][maxn], b[maxn], c[maxn], lg[maxn];
struct ST {
ll f[maxn][12];
void build() {
for (int i = 1; i <= n; ++i) {
f[i][0] = c[i];
}
for (int j = 1; (1 << j) <= n; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
}
inline ll query(int l, int r) {
int k = lg[r - l + 1];
return max(f[l][k], f[r - (1 << k) + 1][k]);
}
} t[maxn];
void solve() {
scanf("%lld%lld%lld%lld%lld", &n, &A, &B, &C, &D);
for (int i = 2; i <= n; ++i) {
lg[i] = lg[i >> 1] + 1;
}
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
f[i][i] = a[i];
b[i] = b[i - 1] + a[i];
c[i] = b[i - 1] - b[i] - f[i][i];
}
t[1].build();
for (int p = 2; p <= n; ++p) {
mems(c, 0);
for (int i = 1, j = p; j <= n; ++i, ++j) {
f[i][j] = max(a[i] - f[i + 1][j], a[j] - f[i][j - 1]);
if (p <= B) {
f[i][j] = max(f[i][j], b[j] - b[i - 1] - A);
} else {
f[i][j] = max(f[i][j], b[j] - b[i - 1] - A + t[p - B].query(i, i + B));
}
if (p <= D) {
f[i][j] = max(f[i][j], b[j] - b[i - 1] - C);
} else {
f[i][j] = max(f[i][j], b[j] - b[i - 1] - C + t[p - D].query(i, i + D));
}
c[i] = b[i - 1] - b[j] - f[i][j];
}
t[p].build();
}
printf("%lld\n", f[1][n]);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}