CSP-J 2024扑克牌问题：贪心算法的经典应用

题目重述与分析

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

核心考点：

• 区间DP与博弈论结合

• 最优子结构性质

• 记忆化搜索实现

算法设计思路

1. 状态定义：

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

2. 转移方程：

   dp[l][r] = max(a[l] - dp[l+1][r], a[r] - dp[l][r-1])

3. 边界条件：

• 当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;
}

关键代码解析

1. 记忆化搜索：

• memo数组存储已计算区间结果

• 初始值为-1表示未计算

2. 递归逻辑：

• takeLeft表示取左端后的净收益

• takeRight表示取右端后的净收益

3. 时间复杂度：

• O(n²) 通过记忆化避免重复计算