题目重述与分析 给定n张扑克牌，每张牌有分值a_i。玩家轮流取牌，每次可从两端取一张，最终获得取牌分值和。双方均采取最优策略，求先手能获得的最大分数差。

核心考点：

区间DP与博弈论结合

最优子结构性质

记忆化搜索实现

算法设计思路 状态定义：

dp[l][r]表示区间[l,r]内先手能获得的最大分差

转移方程：

dp[l][r] = max(a[l] - dp[l+1][r], a[r] - dp[l][r-1]) 边界条件：

当l=r时，dp[l][r]=a[l]

完整C++实现

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1010;
int a[N], memo[N][N];

int dfs(int l, int r) {
    if (l > r) return 0;
    if (memo[l][r] != -1) return memo[l][r];

    int takeLeft = a[l] - dfs(l+1, r);
    int takeRight = a[r] - dfs(l, r-1);

    return memo[l][r] = max(takeLeft, takeRight);
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];

        memset(memo, -1, sizeof memo);
        cout << dfs(0, n-1) << endl;
    }
    return 0;
}

贪心算法