5

问题如下：

Lazer Tag 由小组游戏组成，在整个游戏过程中，您会被分配固定数量的子弹（通常称为激光射击）。对目标敌人的每一次正确射击都会给你一分。

考虑一下一系列的命中和未命中，可以用“x”和“o”的形式表示，其中“o”代表命中，“x”代表未命中。假设系列的形​​式是“xxxoooxxxxooxxo”，那么您的最终得分将等于，3^2 + 2^2 +1^2即在整个游戏过程中将每个最大连续命中数的平方相加。

正确击中第 j 杆的概率（1≤j≤n）为 P(j)。简而言之，在第 j 轮系列中获得“o”的概率是 P(j)。您需要在回合结束时计算预期分数。

我可以理解使用记忆的 O(n^2) 解决方案，但问题需要 O(n) 解决方案。我已经看到了 O(n) 解决方案，但我无法理解它。O(n) 解如下：

for(i = 1; i <= n; i++)
    dp[i] = (dp[i-1] + p[i-1]) * p[i];   
for(i = 1; i <= n; i++)
    ans+=2 * dp[i] + p[i];

其中 p[i] 是命中第 i 个目标的概率。谁能解释 O(n) 解决方案的工作原理？

4

1 回答 1

4

您可以通过以下方式考虑评分：

  1. 每击得 1 分
  2. 每次击球长度 > 1 得分 2 分（多次重复得分）

例如，xxooox 的序列将得分：

  1. 每个 o 的 +1
  2. +2 为 ooo
  3. 第一次 oo +2
  4. +2 第二次 oo

分数 = 1*3+2*3 = 3+6 = 9 分。（这符合原来的打分方式，因为9=3*3）

dp[i] 计算在位置 i 结束的长度 >1 的预期运行次数。

因此，要计算总预期分数，我们需要将 2*dp[i] 相加（因为我们每次运行获得 2 分），加上 p[i] 的总和，以添加每次命中获得 1 分的预期分数。

递归关系是因为在位置 i 结束的长度 >1 的预期运行次数将是：

  1. +1 如果我们从位置 i 开始新的运行，在 i 和 i-1 处命中（概率 p[i]*p[i-1]）
  2. +dp[i-1] 如果我们通过再次命中（概率 p[i]）继续在位置 i-1 结束的运行
于 2013-10-30T19:57:47.787 回答