解题思路

题意分析

题目描述了在放置多米诺骨牌的过程中，由于可能出现放置错误（即多米诺骨牌倒下），且倒下的多米诺骨牌会推倒相邻一侧的连续多米诺骨牌，从而破坏已放置好的骨牌布局。已知要放置的多米诺骨牌数量 $n$，以及单个多米诺骨牌放置时向左倒下的概率 $P_l$ 和向右倒下的概率 $P_r$（且满足 $0 < P_l + P_r \leq 0.5$），需要确定在完成所有骨牌放置之前，平均需要放置的骨牌数量，并且要采用最优的放置策略。

解题思路

1. 定义状态和状态转移方程：
   • 定义 $dp[i]$ 表示放置 $i$ 个多米诺骨牌在完成之前需要放置的平均骨牌数量。显然，$dp[0] = 0$（不需要放置骨牌时，平均放置数量为 0），$dp[1] = \frac{1}{1 - P_l - P_r}$（放置 1 个骨牌时，成功放置的概率为 $1 - P_l - P_r$，根据概率期望公式，平均放置次数为其倒数）。
   • 对于 $i > 1$ 的情况，考虑在放置第 $i$ 个骨牌时的最优放置位置。假设将第 $i$ 个骨牌放置在已放置的骨牌序列中，把已放置的骨牌分为左边 $j$ 个和右边 $i - j - 1$ 个（$0 \leq j < i$）。则状态转移方程为 $dp[i] = \frac{1 - P_r}{1 - P_l - P_r} \times dp[j] + \frac{1 - P_l}{1 - P_r - P_l} \times dp[i - j - 1] + \frac{1}{1 - P_l - P_r}$。这里的 $\frac{1 - P_r}{1 - P_l - P_r} \times dp[j]$ 表示第 $i$ 个骨牌向右倒下时的期望放置数量，$\frac{1 - P_l}{1 - P_r - P_l} \times dp[i - j - 1]$ 表示第 $i$ 个骨牌向左倒下时的期望放置数量，$\frac{1}{1 - P_l - P_r}$ 表示第 $i$ 个骨牌成功放置的情况。
2. 寻找最优放置位置：
   • 对于每个 $i$，需要遍历所有可能的放置位置 $j$（$0 \leq j < i$），计算出相应的 $dp[i]$ 值，并取最小值，即 $dp[i] = \min_{0 \leq j < i} \{ \frac{1 - P_r}{1 - P_l - P_r} \times dp[j] + \frac{1 - P_l}{1 - P_r - P_l} \times dp[i - j - 1] + \frac{1}{1 - P_l - P_r} \}$。
   • 在代码中，通过一个内层循环来实现这一过程。同时，为了优化计算，利用了一个小技巧：记录上次找到最优值的位置 $lp$，从 $lp + 1$ 开始遍历，当发现某个位置 $j$ 计算出的 $dp[i]$ 值大于当前的 $dp[i]$ 值时，就可以停止遍历，因为后面的位置计算出的值会更大（根据问题的性质，通常存在这样的单调性）。
3. 输出结果：
   • 经过上述动态规划过程，计算出的 $dp[n]$ 即为放置 $n$ 个多米诺骨牌在完成之前需要放置的平均骨牌数量，按照要求精确到小数点后两位数输出。

##参考代码

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
const int maxn = 1010;
double dp[maxn];
int n;
double pl, pr;
 
double cal(int l, int r) {
    return (1 - pr) / (1 - pl - pr) * dp[l] + (1 - pl) / (1 - pr - pl) * dp[r] + 1.0 / (1 - pl - pr);
}
 
int main() {
    while (scanf("%d", &n) && n) {
        scanf("%lf %lf", &pl, &pr);
        dp[0] = 0;
        dp[1] = 1.0 / (1 - pl - pr);
        
        for (int i = 2; i <= n; ++i) {
            dp[i] = cal(0, i - 1);
            for (int j = 1; j < i; ++j) {
                double t = cal(j, i - j - 1);
                if (t < dp[i]) {
                    dp[i] = t;
                }
            }
        }
        
        printf("%.2lf\n", dp[n]);
    }
    return 0;
}