「POI2010」最小化游戏 题解

题目分析

Alice 和 Bob 轮流从一组数字卡片中选择若干张牌，每次选择的得分等于所选牌中数字的最小值。两人都希望最大化自己与对手的分数差，需要计算在双方都采用最优策略时的最终分数差。

解题思路

关键观察

1. 排序的重要性：由于得分取决于所选牌的最小值，将卡片按升序排序后，当我们选择某个位置的卡片时，实际上选择了从该位置开始到某个结束位置的所有卡片（因为选择更大的数字不会降低最小值）。

2. 动态规划状态设计：定义 dp[i] 表示考虑前 i+1 张牌（索引 0 到 i）时，当前玩家能获得的最大分数优势。

3. 状态转移方程：

   • 如果当前玩家选择包含第 i 张牌的一组牌，那么这组牌的最小值就是 karty[i]
   • 选择后，剩下的牌由对手在最优策略下游戏，对手会获得 dp[i-1] 的优势
   • 因此当前玩家的优势为：karty[i] - dp[i-1]
   • 当前玩家也可以不选择包含第 i 张牌的组，那么优势保持为 dp[i-1]
   • 所以状态转移方程为：dp[i] = max(dp[i-1], karty[i] - dp[i-1])

算法步骤

1. 读入所有卡牌数字
2. 对卡牌进行升序排序
3. 初始化 dp[0] = karty[0]（只有一张牌时直接拿走）
4. 按状态转移方程计算所有 dp[i]
5. 输出 dp[n-1] 作为最终结果

复杂度分析

• 时间复杂度：O(n log n)，主要来自排序操作
• 空间复杂度：O(n)，用于存储卡牌和 DP 数组

代码实现

#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

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

    if (n == 0) {
        printf("0\n");
        return 0;
    }

    // 将卡牌按升序排序
    sort(karty.begin(), karty.end());

    vector<long long> dp(n);
    dp[0] = karty[0];  // 只有一张牌时直接拿走
    
    for (int i = 1; i < n; i++) {
        // 状态转移：选择包含当前牌或不选择
        dp[i] = max(dp[i - 1], (long long)karty[i] - dp[i - 1]);
    }

    printf("%lld\n", dp[n - 1]);
    return 0;
}

示例解释

对于样例输入：

3
1 3 1

排序后得到：[1, 1, 3]

计算过程：

• dp[0] = 1
• dp[1] = max(1, 1 - 1) = max(1, 0) = 1
• dp[2] = max(1, 3 - 1) = max(1, 2) = 2

最终输出 2，表示 Alice 比 Bob 多 2 分。

总结

这道题通过排序和动态规划巧妙解决了博弈问题。核心在于理解选择某张牌意味着选择了它及其之后的所有牌，以及通过动态规划来模拟双方的最优策略选择。