程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 10529 Dumb Bones 概率dp 求期望

UVA 10529 Dumb Bones 概率dp 求期望

編輯：C++入門知識

UVA 10529 Dumb Bones 概率dp 求期望

題目鏈接：點擊打開鏈接

題意：

要在一條直線上擺多米諾骨牌。

輸入n, l, r

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

可以采取最優策略，即可以中間放一段，然後左右兩邊放一段等，擺放順序任意。

問：在最佳策略下要擺成n張牌的期望次數。

思路：

點擊打開鏈接

#include 
#include 
#include 
#include 
#include 
#include 
#include 
template 
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 
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;
}