设状态 F(L, R) : 该回合先手能在区间 [L,R] 中获得的最大价值。
边界条件: L == R, 则该回合的先手一定会选择这个价值。
状态转移方程:
$$
F(L, R) = Max(选择 L 下标处的价值 + 在区间[L + 1, R]后手能获得的最大值, 选择 R 下标处的价值 + 在区间[L, R - 1]后手能获得的最大值)
$$
- 其中 $ 后手能获得的值 = 区间和 - 先手能获得的值 $
#include <iostream>
using namespace std;
const int N = 110;
int n, a[N], sum[N], f[N][N];
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
for(int len = 1; len <= n; ++len) {
for(int i = 1; i + len - 1 <= n; ++i) {
int j = i + len - 1;
if(len == 1) f[i][j] = a[i];
else f[i][j] = max(f[i][j], max(a[i] + sum[j] - sum[i] - f[i + 1][j], a[j] + sum[j - 1] - sum[i - 1] - f[i][j - 1]));
}
}
cout << f[1][n] << ' ' << sum[n] - f[1][n];
return 0;
}