POJ 2327 - Dumb Bones

http://poj.org/problem?id=2327

概要

\(n\) 個のドミノを一列に連続して並べたい。 しかし、あるドミノを置いたとき、確率 \(P_l\) で左側に倒れてしまい、確率 \(P_r\) で右側に倒れてしまう。 倒してしまうと、そこから連続したドミノはすべて倒れてしまう。

1ステップで1つのドミノを置くとき、最適な方法で \(n\) 個並べきるのに必要なステップ数の期待値を答える。

制約

解法

DP。 最適に \(k\) 個置いたときの期待値を dp[k] とする。 今、左側に連続して \(l\) 個、右側に連続して \(r\) 個並んでおり、この間に新たに1つ置いて連続して \(l+1+r\) 個並べたいとする。 すると、この1個置いたときに考えられる事象は

  1. 倒れない (確率 \(1 - P_l - P_r\))
  2. 左側に倒れる (確率 \(P_l\))
  3. 右側に倒れる (確率 \(P_r\))

のいずれかである。 ここから1つ増やすのに必要なステップ数の期待値を \(x\) とすると、左側の \(l\) 個並べたときの期待値を \(E_l\)、右側の \(r\) 個並べたときの期待値を \(E_r\) として、

  1. の場合、新たに1個置くだけなので \(1\) ステップかかる
  2. の場合、新たに1個置いて左側を倒し、再び \(l\) 個並べるのに \(E_l\) ステップかかり、さらにもう1つ置くのに \(x\) ステップで、合計 \(1 + E_l + x\) ステップかかる
  3. の場合も同様に \(1 + E_r + x\) ステップかかる

であるので、\(x = (1 - P_l - P_r) \cdot 1 + P_l \cdot (1 + E_l + x) + P_r \cdot (1 + E_r + x)\) が成り立ち、これを解いて \(x = \frac{1 + P_l E_l + P_r E_r}{1 - P_l - P_r}\) となる。 よって、dp[l+1+r] を \(E_l + x + E_r\) で更新すればいい。

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N;
 8   while (scanf("%d", &N) != EOF && N != 0) {
 9     double Pl, Pr;
10     scanf("%lf %lf", &Pl, &Pr);
11 
12     vector<double> dp(N+1, 1e10);
13     dp[0] = 0;
14     for (int i = 1; i <= N; i++) {
15       for (int j = 0; j < i; j++) {
16         const double El = dp[j], Er = dp[i-j-1];
17         const double x = (1 + Pl*El + Pr*Er)/(1 - Pl - Pr);
18         dp[i] = min(dp[i], El + Er + x);
19       }
20     }
21     printf("%.2f\n", dp[N]);
22   }
23   return 0;
24 }
poj/2327.cc