uva 10529 - Dumb Bones(概率+区间dp)

题目连接：uva 10529 - Dumb Bones

题目大意：给定n，表示要放n个骨牌，每次放下骨牌，有可能向左倒的概率为pl，向右倒的概率为pr，如果倒下，会将那一侧的骨牌全部推倒，可以选择位置先后放骨牌，问说一种放骨牌次数最少的期望是多少。

解题思路：dp[i]表示放i个骨牌需要的步数期望，维护一个最优放的位置，dp[i]=min\{（从i-1到i的步数）}+（0到i-1的步数）}

• （从i-1到i的步数）：dp[i−j−1]∗pl+dp[j]∗pr+11−pl−pr
• （0到i-1的步数）:dp[j]+dp[i−j−1]

so: dp[i]=min{dp[i−j−1]∗pl+dp[j]∗pr+11−pl−pr+dp[j]+dp[i−j−1]}

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int maxn = 1005;
const double INF = 0x3f3f3f3f3f3f3f;

int N;
double pl, pr, dp[maxn];

double solve () {
    double ac = 1 - pl - pr;

    for (int i = 1; i <= N; i++) {
        dp[i] = INF;
        for (int j = 0; j < i; j++) {
            double tmp = dp[i-j-1] * pl + dp[j] * pr;
            tmp = dp[j] + dp[i-j-1] + (tmp + 1) / ac;
            if (tmp < dp[i])
                dp[i] = tmp;
        }
    }
    return dp[N];
}

int main () {
    while (scanf("%d", &N) == 1 && N) {
        scanf("%lf%lf", &pl, &pr);
        printf("%.2lf\n", solve());
    }
    return 0;
}