5

問題は次のとおりです。

レーザー タグはグループ プレイで構成されており、ゲーム全体で決まった数の弾丸 (一般にレーザー ショットとして知られています) が割り当てられます。ターゲットの敵を正しく撃つたびに、1 ポイントが与えられます。

「x」と「o」の形で表すことができる一連のヒットとミスを考えてみてください。「o」はヒットを表し、「x」はミスを表します。シリーズが「xxxoooxxxxooxxo」の形式であると仮定すると、最終的なスコアは次のようになります。3^2 + 2^2 +1^2つまり、ゲーム プレイ全体での連続ヒットの最大数の 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 for ooo
  3. 最初の oo は +2
  4. 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 でヒットすることにより、位置 i から始まる新しい実行がある場合は +1 (確率 p[i]*p[i-1])
  2. +dp[i-1] 別のヒットを取得して、位置 i-1 で終了するランを続行する場合 (確率 p[i])
于 2013-10-30T19:57:47.787 に答える