UVA10529 Dumb Bones

设$f[i]$表示叠$i$个的骨牌的期望

$O(n)$做法

#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
using namespace std;
double pl,pr,f[1002]; int n;
double dp(int i,int j){
    return f[j]+f[i-j-1]+(1+pl*f[j]+pr*f[i-j-1])/(1-pl-pr);
}//两块的期望值加上立最后一个骨牌的期望值
int main(){
    while(1){
        scanf("%d",&n);
        if(!n) break;
        scanf("%lf%lf",&pl,&pr);
        for(re int i=1,j=0;i<=n;++i){
            while(j<i-1&&dp(i,j+1)<dp(i,j)) ++j; //j单调不下降
            f[i]=dp(i,j);
        }
        printf("%.2lf
",f[n]);
    }return 0;
}