[LeetCode] 1872. 石子游戏 VIII (c++)-一一网

? “Offer 驾到，掘友接招！我正在参与2022春招打卡活动点击查看活动详情。

1872. 石子游戏 VIII

Alice 和 Bob 玩一个游戏，两人轮流操作， Alice 先手。

总共有 n 个石子排成一行。轮到某个玩家的回合时，如果石子的数目大于 1 ，他将执行以下操作：

选择一个整数 x > 1 ，并且移除最左边的 x 个石子。
将移除的石子价值之和累加到该玩家的分数中。
将一个新的石子放在最左边，且新石子的值为被移除石子值之和。
当只剩下一个石子时，游戏结束。

Alice 和 Bob 的分数之差为 (Alice 的分数 – Bob 的分数) 。 Alice 的目标是最大化分数差，Bob 的目标是最小化分数差。

给你一个长度为 n 的整数数组 stones ，其中 stones[i] 是从左边起第 i 个石子的价值。请你返回在双方都采用最优策略的情况下，Alice 和 Bob 的分数之差。

示例 1：
输入：stones = [-1,2,-3,4,-5]
输出：5
解释：
- Alice 移除最左边的 4 个石子，得分增加 (-1) + 2 + (-3) + 4 = 2 ，并且将一个价值为 2 的石子放在最左边。stones = [2,-5] 。
- Bob 移除最左边的 2 个石子，得分增加 2 + (-5) = -3 ，并且将一个价值为 -3 的石子放在最左边。stones = [-3] 。
两者分数之差为 2 - (-3) = 5 。

示例 2：
输入：stones = [7,-6,5,10,5,-2,-6]
输出：13
解释：
- Alice 移除所有石子，得分增加 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 ，并且将一个价值为 13 的石子放在最左边。stones = [13] 。
两者分数之差为 13 - 0 = 13 。

示例 3：
输入：stones = [-10,-12]
输出：-22
解释：
- Alice 只有一种操作，就是移除所有石子。得分增加 (-10) + (-12) = -22 ，并且将一个价值为 -22 的石子放在最左边。stones = [-22] 。
两者分数之差为 (-22) - 0 = -22 。
复制代码

提示：

n == stones.length
2 <= n <= 10^5
-10^4 <= stones[i] <= 10^4

解题思路：

看到 Alice 和 Bob，就知道是博弈问题。
仔细考虑下，实际上每个人所取的石子的和是前缀和
然后提炼下问题的核心：

Alice和Bob都是想在序列中取到最大的前缀和
Alice先手，Bob后手
两人依次进行，当前取到的前缀和的位置总大于上一次取前缀和的位置

prefixSum[i] = prefixSum[i - 1] + stones[i + 1]

这里前缀和是按照这样的方式存储的，没有存放0位置的前缀和是因为取石子的时候最少要取两个，所以不用考虑0这个位置。

我们假定Alice取第i号位置的话，Bob就会从i + 1开始的位置里面选择差值最大的位置。这里用ret保存最后的结果

ret = max(ret, prefixSum[i] - *suffix.rbegin());

suffix.insert(prefixSum[i] - *suffix.rbegin());

代码如下：

class Solution {
public:
    int stoneGameVIII(vector<int>& stones) {
        // 统计前缀和
        vector<int> prefixSum(stones.size(), 0);
        
        prefixSum[0] = stones[0] + stones[1];
        for(int i = 1; i < stones.size() - 1; ++i){
            prefixSum[i] = prefixSum[i - 1] + stones[i + 1];
        }
        set<int> suffix;
        int ret = prefixSum[stones.size() - 2];
        suffix.insert(prefixSum[stones.size() - 2]);

        for(int i = stones.size() - 3; i >= 0; --i){
            ret = max(ret, prefixSum[i] - *suffix.rbegin());
            suffix.insert(prefixSum[i] - *suffix.rbegin());
        }
        return ret;
    }
};
复制代码