526互联

AtCoder Beginner Contest 303 G Bags Game

发布时间 2023-05-28 19:22:22作者: zltzlt

洛谷传送门

AtCoder 传送门

经典题，考虑区间 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;
}