博弈论 + 区间DP

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int w[N];
int f[N][N];  // 表示在区间 [i,j]时，先手和后手的最大差值得分。

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &w[i]);

    for (int len = 1; len <= n; len ++ )
        for (int i = 0; i + len - 1 < n; i ++ )
        {
            int j = i + len - 1;
            // 我们选择区间端点 i，对方面对的是在[i + 1, j]进行选择
            // [i + 1, j]时，对方相当于先手
            // 区间端点 j 同理
            f[i][j] = max(w[i] - f[i + 1][j], w[j] - f[i][j - 1]);
        }

    int sum = 0, d = f[0][n - 1];
    for (int i = 0; i < n; i ++ ) sum += w[i];

    printf("%d %d\n", (sum + d) / 2, (sum - d) / 2);
    return 0;
}