题意:
给出放一个多米诺骨牌,向左向右倒的概率,求要放好n个骨牌,需要放置的骨牌的期望次数。
分析:
用到区间dp的思想,如果一个位置的左面右面骨牌都已放好,考虑,放中间的情况,
dp[i]表示放好前i个骨牌,要放的期望次数,枚举1-i,每个点做中间点求对应的期望,取最小值。
dp[i]=min(L*dp[l]+R*dp[r]+1/(1.0-L-R));
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define All 1,N,1
#define read freopen("in.txt", "r", stdin)
const ll INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod = ;
double dp[],l,r;
int n;
void solve(){
dp[]=;
dp[]=1.0/(-l-r);
for(int i=;i<=n;++i){
dp[i]=INF;
for(int j=;j<i;++j){
double tmp=((1.0-r)*dp[j]+(1.0-l)*dp[i-j-]+)/(1.0-l-r);
dp[i]=min(dp[i],tmp);
}
}
printf("%.2lf\n",dp[n]);
}
int main()
{
while(~scanf("%d",&n)){
if(n==)break;
scanf("%lf%lf",&l,&r);
solve();
}
return ;
}