1

原始问题陈述堆起来

摘要：两个玩家 A 和 B 玩由 2 堆 X 和 Y 硬币组成的游戏。每一轮他都可以做以下事情之一：

  • 从一堆硬币中取出任意数量的硬币（至少 1 个硬币）
  • 从两堆中取出相同数量的硬币
  • 转弯通过。这仍然算一回合。

当无法移动且无法移动的玩家输掉时，游戏结束。两名球员都发挥最佳。双方玩家在比赛开始前计算比赛结果。输的玩家试图最大化游戏中的回合数，而获胜的玩家试图最小化回合。没有玩家可以传球超过 P 次。A 开始游戏。输出获胜者的姓名和游戏中的移动次数，以单个空格分隔。0 <= X, Y, P <= 1000

我想出了一个 O(n^3) DP 解决方案，但考虑到界限，它肯定不足以解决这个问题。如果轮到你玩并且 X 和 Y 堆分别剩下 i 和 j 个硬币，则设 d[i, j] 为获胜的最小回合数。然后我们有：

d[i, j] = 0 if i = j = 0
          1 if (i = 0 && j > 0) or (i > 0 && j = 0) or (i = j && i > 0)
          min(min(d[i-p, j]), min(d[i, j-q), min(i-r, j-r)) if a each substate is a losing position
          max of all winning position substate if no losing substate is found

最后，d[i,j] = d[i,j] + 2*P if [i,j]是一个获胜的状态，你不会从一开始就立即获胜。

从上面的公式可以看出，这是一个 O(n^3) 的解决方案。我想改进对 O(n^2) 的解决方案，如何重新表述问题？

4

1 回答 1

1

首先获胜的位置是

  1. 1个空桩
  2. 两堆相同数量的硬币

玩家什么时候轮到他？
假设位置是（3,2），那么他有 3 个选项。

  1. 他可以移动到 (2,2) ，但这对他的对手来说是一个获胜的位置。
  2. 他可以移动到 (1,0)，但这对他的对手来说也是一个获胜的位置。
  3. 如果他选择跳过回合，那么对手也可以跳过回合。这种跳过最多可以进行P回合。

根据 P 的奇偶性（P 是偶数还是奇数）以及根据谁开始跳过序列，我们可以找出获胜的人。从那里找到转数并不难。

为什么跳过序列是最优的？
好吧，如果您输了，您会希望在游戏中停留更长时间。（根据游戏规则。）因此，即使我基于 P 的平价知道我会输，我也可以将其延迟 P 回合。说得通？
我鼓励您使用这种见解来提高您的算法速度，但是如果您在实施它时遇到问题，请务必提出问题！

于 2013-07-08T06:45:28.633 回答