无法理解DP解决方案

Question

5

问题如下：

Lazer Tag 是一个团体游戏，在整个游戏中，你会被分配一个固定数量的子弹（通常称为激光射击）。每一次对目标敌人的精准射击都会给你一个积分。

考虑你的命中和失误的序列，可以用“x”和“o”表示，“o”表示命中，“x”表示未命中。假设序列的形式为“xxxoooxxxxooxxo”，那么你的最终得分将等于每场游戏中连续命中的最大数值的平方之和，即3的平方加2的平方加1的平方。

第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) 解决方案是如何工作的吗？

- SHB

@Chill，这个解决方案是正确的。这是问题链接[http://www.codechef.com/TCFST13/problems/TCFST05/]，我给出的解决方案是其中一个被接受的方案。 - SHB

那么我的模拟肯定有问题。请检查一下，如果您发现任何问题，请告诉我。http://pastebin.com/NHWgK1fZ - Chill

“o” 代表命中，“x” 代表未命中。为什么？ - j_random_hacker

@j_random_hacker “o代表命中，‘x’代表未命中”，这只是问题的表述方式，与解决方案无关。 dp[0]在开始时包含0。 - SHB

1

@user2094963：这不是一个严肃的评论。我想说的是99%的情况下，“X”表示“命中”，“O”表示“未命中”。这就像问题谈论一个交通信号灯，使用红色表示“前进”，绿色表示“停止”一样 :-P - j_random_hacker

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter de Rivaz · Accepted Answer

您可以这样理解得分：

1. 每个命中得1分。 2. 对于长度>1的所有连续命中，每个连续命中都得2分（重叠的连续命中得分多次）。

例如，序列xxooox将得分：

+每个o得1分 + ooo得2分 +第一个oo得2分 +第二个oo得2分

得分= 1 * 3 + 2 * 3 = 3 + 6 = 9分。（因为9 = 3 * 3，所以这与原始得分方式相匹配）

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

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

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

1.如果我们通过在i和i-1处击中来开始新的运行，则+1（概率为p [i] * p [i-1]） 2.如果我们通过获得另一个命中来继续在位置i-1结束的运行，则+dp [i-1]（概率为p [i]）