题目重述与分析
给定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;
}