UVA 10529 Dumb Bones 可能性dp 需求预期

主题链接：点击打开链接

题意：

要在一条直线上摆多米诺骨牌。

输入n, l, r

要摆n张排，每次摆下去向左倒的概率是l, 向右倒的概率是r

能够採取最优策略。即能够中间放一段。然后左右两边放一段等，摆放顺序随意。

问：在最佳策略下要摆成n张牌的期望次数。

思路：

点击打开链接

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
template <class T>
inline bool rd(T &ret) {
    char c; int sgn;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?

0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } template <class T> inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if(x>9) pt(x/10); putchar(x%10+'0'); } using namespace std; typedef long long ll; #define N 2002 const ll mod = 1e9+7; int n; double l, r; double dp[N]; double solve(){ dp[0] = 0; dp[1] = 1.0/(1.0-l-r); for(int i = 2; i <= n; i++) { dp[i] = 1e18; for(int j = 0; j < i; j++) { int L = j, R = i-j-1; double x = (1+ dp[L] + dp[R] -dp[L]*r -dp[R]*l) / (1-l-r); dp[i] = min(dp[i], x); } } return dp[n]; } int main() { while(cin>>n>>l>>r, n){ printf("%.2f\n", solve()); } return 0; }