零崎的悠哉日常Ⅲ，悠哉

零崎的悠哉日常Ⅲ，悠哉

題目來源：https://biancheng.love/contest-ng/index.html#/34/problems

題目描述

零崎在空閒時間很多的時候，就喜歡玩一些非常耗時間的游戲，比如可以死上幾千次的I wanna，又比如一不小心就要重頭開始的多米諾骨牌。

在擺放多米諾骨牌時，如果中途碰倒一塊，就會產生雪崩般的影響。比如說11__1x11_11這種形狀，零崎這麼作死的人當然會在中間x位置放一枚骨牌……這種作死的做法有pl的概率會倒向左邊並把左邊的1個骨牌碰倒，或者有pr的概率會倒向右邊並把右邊的2個都碰倒。（骨牌不是量子態不會既左倒又右倒……）

現在零崎准備把手裡的N枚多米諾骨牌擺成一條直線，那麼他擺放骨牌次數的期望是多少？

輸入

多組輸入數據。

每組數據為三個數，第一個為整數N<10000，接下來兩個浮點數pl，pr，0<pl+pr<1

輸出

對於每組數據，輸出一行，為采取最佳擺放方式時的次數期望，保留兩位小數

輸入樣例

2 0.1 0.1
10 0.2 0.3

輸出樣例

2.66
44.03

Hint

幾何分布的期望Ex=1/p

O(n^2)可過

代碼：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define INF 0x3f3f3f3f
const int N = 1000005;
int n;
double p, pl, pr, dp[N];

double cal(int l, int r) {
  return dp[l] + dp[r] + (pl * dp[l] + pr * dp[r] + 1) / p;
}

double solve() {
  p = 1 - pl - pr;
  dp[0] = 0; dp[1] = 1 / p;
  int pre = 0;
  for (int i = 2; i <= n; i++) {
  dp[i] = cal(pre, i - pre - 1);
  for (int j = pre + 1; j < i; j++) {
    int l = j, r = i - 1 - j;
    double tmp = cal(l, r);
    if (dp[i] >= tmp) {
    dp[i] = tmp;
    pre = j;
    }
    else break;
  }
  }
  return dp[n];
}

int main() {
  while (~scanf("%d", &n) && n) {
  scanf("%lf%lf", &pl, &pr);
  printf("%.2lf\n", solve());    
  }
  return 0;
}