算法
(区间DP) $O(N^2)$
记 dp[l][r]
表示在区间 $[l, r)$ 中二者分差的最大值
为了最大化 $X-Y$,先手应该每次取剩下的那段区间里能让分差最大化的那一端的分数
然后用记忆化搜索跑一遍区间 $\operatorname{dp}$ 会比较简单
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using ll = long long;
const ll INF = 1e18;
template<typename T>
inline void chmax(T& x, T y) { if (x < y) x = y; }
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector dp(n, vector<ll>(n+1));
vector memo(n, vector<bool>(n+1));
auto dfs = [&](auto& f, int l, int r) -> ll { // [l, r)
if (l == r) return 0;
if (memo[l][r]) return dp[l][r];
memo[l][r] = true;
ll res = -INF;
chmax(res, a[l]-f(f, l+1, r));
chmax(res, a[r-1]-f(f, l, r-1));
return dp[l][r] = res;
};
ll ans = dfs(dfs, 0, n);
cout << ans << '\n';
return 0;
}