「切糕游戏」题解

问题分析

这是一个两人零和博弈问题：Kiana 切糕并选择顺序，Tinytree 决定是否使用优先选糕权。两人都足够聪明，目标是最大化自己获得的切糕总量。

关键观察

1. 游戏过程：

   • Kiana 选择一块糕切成两份（可以任意比例）
   • Tinytree 决定是否使用优先权
   • 选择完成后，剩余优先权次数会减少（如果使用了）

2. 博弈结构：

   • 这是一个完全信息博弈：双方都知道所有糕的大小
   • 这是一个序贯博弈：Kiana 先行动，然后 Tinytree 响应
   • 双方都采取最优策略

问题转化

单个切糕的博弈分析

考虑当前只剩一块大小为 $a$ 的糕，Tinytree 还剩 $j$ 次优先权：

1. 如果 Tinytree 没有优先权（$j=0$）：

   • Kiana 会将糕切成 $(a, 0)$
   • 自己选择 $a$，Tinytree 得到 $0$
   • Kiana 收益：$a$

2. 如果 Tinytree 有优先权（$j>0$）：

   • 设 Kiana 将糕切成 $(x, a-x)$，其中 $0 \leq x \leq a/2$（不失一般性设 $x \leq a-x$）
   • Tinytree 的决策：
     • 如果使用优先权，会选择较大的 $a-x$，Kiana 得到 $x$
     • 如果不使用，Kiana 会选择较大的 $a-x$，Tinytree 得到 $x$
   • Tinytree 会比较：$a-x$（使用优先权） vs $x$（不使用）
   • 因此 Tinytree 会使用优先权当且仅当 $a-x > x$，即 $x < a/2$

   Kiana 的优化问题：选择 $x$ 最大化自己的收益：

   • 如果 $x < a/2$：Tinytree 使用优先权，Kiana 得到 $x$
   • 如果 $x \geq a/2$：Tinytree 不使用优先权，Kiana 得到 $a-x$

   因此最优策略是：

   • 如果想让 Tinytree 使用优先权，则设 $x$ 尽可能大但仍小于 $a/2$
   • 如果想让 Tinytree 不使用优先权，则设 $x = a/2$
   • 实际上，最优的 $x = \min(a/2, p)$，其中 $p$ 是一个临界值

多个切糕的动态规划

我们需要考虑剩余优先权次数对博弈的影响。

定义 $dp[i][j]$：考虑从第 $i$ 块到第 $n$ 块糕（排序后），Tinytree 还剩 $j$ 次优先权时，Kiana 能获得的最大总大小。

状态转移

假设我们已按从大到小排序了糕的大小：$a_1 \geq a_2 \geq \cdots \geq a_n$

对于当前糕 $a_i$ 和剩余优先权 $j$：

1. Tinytree 没有优先权（$j=0$）：

   $$dp[i][0] = a_i + dp[i+1][0]$$

2. Tinytree 有优先权（$j>0$）： 设 Kiana 将 $a_i$ 切成 $(x, a_i-x)$，$x \leq a_i/2$

   Tinytree 的决策：

   • 使用优先权：得到 $a_i-x$，消耗1次优先权，剩余 $j-1$
   • 不使用：得到 $x$，剩余 $j$

   Tinytree 会选择对自己更有利的方案，即比较：

   • $a_i-x + dp[i+1][j-1]$（使用）
   • $x + dp[i+1][j]$（不使用）

   设临界值 $p$ 使得两者相等：

   $$a_i - p + dp[i+1][j-1] = p + dp[i+1][j]$$

   解得：

   $$p = \frac{a_i + dp[i+1][j] - dp[i+1][j-1]}{2}$$

   现在 Kiana 选择 $x$ 来最大化收益：

   • 如果 $x < p$：Tinytree 使用优先权，Kiana 得到 $x$
   • 如果 $x \geq p$：Tinytree 不使用优先权，Kiana 得到 $a_i-x$

   因此 Kiana 的最优选择是：

   • 如果 $p \leq 0$：设 $x=0$，Tinytree 不使用优先权，Kiana 得到 $a_i$
   • 如果 $p \geq a_i/2$：设 $x=a_i/2$，Tinytree 使用优先权，Kiana 得到 $a_i/2$
   • 否则：设 $x=p$，Tinytree 使用优先权，Kiana 得到 $p$

   综上：

   $$dp[i][j] = \begin{cases} a_i + dp[i+1][j], & \text{if } p \leq 0 \\ \frac{a_i}{2} + dp[i+1][j-1], & \text{if } p \geq \frac{a_i}{2} \\ p + dp[i+1][j-1], & \text{otherwise} \end{cases}$$

边界条件

当 $i=n$（最后一块糕）：

• $dp[n][0] = a_n$（Tinytree 无优先权）
• $dp[n][j] = a_n/2$，$j>0$（Tinytree 有优先权）

算法步骤

步骤1：预处理

1. 读取 $n, m$ 和 $a_1, \ldots, a_n$
2. 将糕按大小从大到小排序：$a_1 \geq a_2 \geq \cdots \geq a_n$

步骤2：动态规划

1. 初始化 $dp[n+1][j] = 0$（没有糕时收益为0）
2. 计算最后一块糕：
   • $dp[n][0] = a_n$
   • 对于 $j=1$ 到 $m$：$dp[n][j] = a_n/2$
3. 从 $i=n-1$ 递减到 $1$：
   • $dp[i][0] = a_i + dp[i+1][0]$
   • 对于 $j=1$ 到 $m$：
     • 计算 $p = (a_i + dp[i+1][j] - dp[i+1][j-1])/2$
     • 根据 $p$ 的值选择策略，计算 $dp[i][j]$

步骤3：输出结果

输出 $dp[1][m]$，保留6位小数。

复杂度分析

• 排序：$O(n \log n)$
• 动态规划：状态数 $O(n \times m)$，转移 $O(1)$，总 $O(nm)$
• 总复杂度：$O(n \log n + nm)$
• 对于 $n,m \leq 2500$，$nm \leq 6.25 \times 10^6$，可接受

正确性证明

1. 排序的正确性

将糕从大到小排序是合理的，因为：

• 游戏是序贯的，先处理大糕还是小糕不影响最优解
• 从大到小排序使得动态规划更容易分析

2. 状态转移的正确性

对于每个状态 $(i,j)$：

• Kiana 考虑当前糕 $a_i$ 的切法
• Tinytree 根据 Kiana 的切法决定是否使用优先权
• 双方都采取最优策略，形成子博弈完美均衡

3. 临界值 $p$ 的意义

$p$ 是 Tinytree 使用和不使用优先权无差异的切法。Kiana 可以通过控制 $x$ 的值来影响 Tinytree 的决策，从而最大化自己的收益。

示例验证

以样例为例：$n=4, m=3, a=[4,3,2,1]$

排序后：$[4,3,2,1]$

计算过程：

• $dp[4][0]=1, dp[4][1]=0.5, dp[4][2]=0.5, dp[4][3]=0.5$
• 计算 $dp[3][*]$：
  • $p = (2+dp[4][1]-dp[4][0])/2 = (2+0.5-1)/2 = 0.75$
  • $0 < 0.75 < 1$，所以 $dp[3][1]=0.75+dp[4][0]=0.75+1=1.75$ 等等...

最终 $dp[1][3]=5.25$，与样例一致。

总结

本题是一个经典的博弈论+动态规划问题：

• 将复杂的博弈过程转化为动态规划状态
• 通过分析单步博弈找到最优策略
• 利用排序简化问题
• 最终得到高效算法