问题如下:
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) 的解决方案如下:
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) 解决方案是如何工作的吗?