Skip to content

动态规划

808. 分汤

有 A 和 B 两种类型 的汤。一开始每种类型的汤有 n 毫升。有四种分配操作：

  1. 提供 100ml 的 汤A 和 0ml 的 汤B 。
  2. 提供 75ml 的 汤A 和 25ml 的 汤B 。
  3. 提供 50ml 的 汤A 和 50ml 的 汤B 。
  4. 提供 25ml 的 汤A 和 75ml 的 汤B 。

当我们把汤分配给某人之后，汤就没有了。每个回合，我们将从四种概率同为 0.25 的操作中进行分配选择。如果汤的剩余量不足以完成某次操作，我们将尽可能分配。当两种类型的汤都分配完时，停止操作。

注意 不存在先分配 100 ml 汤B 的操作。

需要返回的值： 汤A 先分配完的概率 + 汤A和汤B 同时分配完的概率 / 2。返回值在正确答案 10-5 的范围内将被认为是正确的。

数据范围：\(n \le 10^9\)

方法一：动态规划

在不关注到数据范围之前，应该不难想到动态规划的做法。把 \(n\) 按照 \(25\) 单元进行划分，变为 \(\lceil n/25 \rceil\)。然后设 \(d[i][j]\) 表示 \(A\) 剩余 \(i\)，\(B\) 剩余 \(j\) 时的概率。

首先分析一下初态：

  • \(d[0][0] = 0.5\)
  • \(d[0][j] = 1, \forall j \in [1, n]\)
  • \(d[i][0] = 0, \forall i \in [1, n]\)

然后，考虑四种转移，注意题目中有一个特殊条件，「如果汤的剩余量不足以完成某次操作，我们将尽可能分配」，所以在转移时要考虑不够的情况：

\[\begin{align}d[i][j] &= d[\max(i-4,0)][j]\\ &+ d[\max(i-3,0)][\max(j-1,0)]\\ &+ d[\max(i-2,0)][\max(j-2,0)]\\ &+ d[\max(i-1,0)][\max(j-3,0)]\end{align}\]

然后，答案就是 \(d[n][n]\)。当然，这个复杂度是 \(O(n^2)\)。但是你会注意到，随着 \(n\) 的增大，这个概率在增加，因为 \(A\) 会更快的被倒完。因此，大胆测试，发现 \(n\) 在 \(5000\) 时，答案已经趋近 1.0。其实这个下限还可以更低：

\[ n=4475,p≈0.999990211307\\ n=4476,p≈0.999990468596 \]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    double soupServings(int n) {
        if (n >= 5000) {
            return 1.0;
        }
        n = (n + 24) / 25;
        vector<vector<double>> d(n + 1, vector<double>(n + 1));
        d[0][0] = 0.5;
        for (int i = 1; i <= n; i++) {
            d[0][i] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] += d[max(i - 4, 0)][j] * 0.25;
                d[i][j] += d[max(i - 3, 0)][max(j - 1, 0)] * 0.25;
                d[i][j] += d[max(i - 2, 0)][max(j - 2, 0)] * 0.25;
                d[i][j] += d[max(i - 1, 0)][max(j - 3, 0)] * 0.25;
            }
        }
        return d[n][n];
    }
};
复杂度分析

  • 时间复杂度：\(O(C^2)\)，这里 \(C = 250\)
  • 空间复杂度：\(O(C^2)\)，这里 \(C = 250\)

截一段网友关于这个题的评论：

本文访问 次