UVA10529 Dumb Bones

题目：Dumb Bones

题意：
来自luogu——
你正在尝试用多米诺骨牌搭成一条直线，以便最后试验时推倒它们
（确实，搭建某些东西仅仅为了推倒看上去没啥意义，但你有一些奇怪的爱好）
然而你在搭建过程中可能会弄倒骨牌，这将波及到邻近的部分
现在需要你来求将骨牌搭建完成所需的期望步数

思路：
令f[i]表示连续i个骨牌搭建的期望步数。
枚举已经搭建了i-1个骨牌，还剩k第k个位置没有搭的中间量k。
比如，当i=5，k=2时描述的就是…_DxDDD_…的状态。
然后通过搭起k左右的连续段进行转移。
即 f[i]= min{ 搭起k右边的期望×向右边倒的概率 + 搭起k左边的期望×向左边倒的概率 +不倒的概率×1 }
转移方程：$f[i] = min(\frac{1+f[r]}{(1-pr-pl)} + \frac{1+f[l]}{(1-pr-pl)} + f[r] + f[l] + 1) = min(\frac{(1-pl)×f[r]}{(1-pr-pl)} + \frac{(1-pr)×f[l]}{(1-pr-pl)} + \frac{1}{(1-pr-pl)}) = min(\frac{(1-pl)×f[r] + (1-pr)×f[l] +1}{1-pr-pl})$
其中 $l=k-1,r=i-k$

代码：

#include<bits/stdc++.h>
using namespace std;#define db double
#define maxn 1000
#define inf (1<<30)int n;
db pl,pr;
db f[maxn+5];int main() {while(~scanf("%d%lf%lf",&n,&pl,&pr)&&n) {for(int i=1;i<=n;i++) {f[i]=inf;for(int j=1;j<=i;j++) {int l=j-1,r=i-j;f[i]=min(f[i],((1-pl)*f[r]+(1-pr)*f[l]+1)/(1-pr-pl));}}printf("%.2lf\n",f[n]);}return 0;
}