题解

方法思路

1.​问题分析​：这个问题类似于“石子游戏”或“取石子游戏”的变种，其中石子排成一排，每次只能从两端取一堆。两位玩家轮流取石子，目标都是最大化自己的得分优势（即X - Y）。我们需要使用动态规划来记录在不同子区间内当前玩家能获得的最大得分差。
​2.动态规划定义​：定义 dp[i][j] 表示当剩下的石子堆是第i堆到第j堆时，当前玩家与对手玩家的得分差的最大值。最终答案是 dp[0][n-1]。
3.​状态转移方程​：
当 i == j 时，即只剩一堆石子，当前玩家只能取这堆石子，所以 dp[i][j] = a[i]。
否则，当前玩家有两种选择：取第i堆或第j堆。取第i堆时，得分为 a[i] - dp[i+1][j]（因为对手会在剩下的区间内采取最优策略，所以减去对手的得分差）。同理，取第j堆时，得分为 a[j] - dp[i][j-1]。当前玩家会选择两者中的较大值，即 dp[i][j] = max(a[i] - dp[i+1][j], a[j] - dp[i][j-1])。
​4.初始化与填表​：我们需要按区间长度从小到大来填充DP表，因为大区间的值依赖于小区间的值。

解决代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<vector<long long>> dp(n, vector<long long>(n, 0));

    for (int i = n - 1; i >= 0; --i) {
        for (int j = i; j < n; ++j) {
            if (i == j) {
                dp[i][j] = a[i];
            } else {
                long long left = a[i] - dp[i + 1][j];
                long long right = a[j] - dp[i][j - 1];
                dp[i][j] = max(left, right);
            }
        }
    }

    cout << dp[0][n - 1] << endl;

    return 0;
}