UVA 10529-Dumb Bones(概率dp)

题意:

给出放一个多米诺骨牌,向左向右倒的概率,求要放好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 ;
}
上一篇:转载 BCS 的好文章 1 - 怎么创建和使用BCS


下一篇:github page 构建自己的页面