POJ 2327 - Dumb Bones

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

概要

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

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

制約

• $1 \le n \le 1000$
• $0 < P_l + P_r \le 0.5$

解法

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 }