C++前缀和算法的应用：石头游戏 VIII 原理源码测试用例

本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

题目

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 public: int stoneGameVIII(vector m_c = stones.size(); //dp[i]表示剩余i个石头时，(先手方分数-后手方分数)的最大值 m_dp.resize(m_c + 1); //计算dp[i]时，假定移除石头后，还剩j个,也就是移除m_c-j个 // j的取值范围[0,i) 且m_c-j1 // cur = stones[0,m_c-j)个石头的价值和 - dp[j] vector 0 }; for (const auto& n : stones) { vSum.emplace_back(n + vSum.back()); } int iMax = vSum[m_c - 0]-m_dp[0]; for (int i = 1; i m_dp[i] = iMax; if (m_c - i 1) { iMax = max(iMax, vSum[m_c - i] - m_dp[i]); } } return m_dp.back(); } int m_c; vector= 1; i–)

  {

  dp[i] = max(dp[i + 1], preSum[i] - dp[i + 1]);

  }

  return dp[1];

  }

  int m_c;

  };

  扩展阅读

  视频课程

  有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

  https://edu.csdn.net/course/detail/38771

  如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

  https://edu.csdn.net/lecturer/6176

  相关下载

  想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版

  https://download.csdn.net/download/he_zhidan/88348653

  | 鄙人想对大家说的话

  |

  |-|

  |闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。|

  | 墨家名称的来源：有所得以墨记之。 |

  |如果程序是一条龙，那算法就是他的是睛|

  测试环境

  操作系统：win7 开发环境： VS2019 C++17

  或者 操作系统：win10 开发环境： VS2022 C++17