The Moon HDU6558（期望/概率dp/记忆化dp）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6558

题意很好理解，造着他意思记忆化dp下就好。 s o l v e ( p , q ) = p ∗ q + p ∗ ( 1 − q ) ∗ ( s o l v e ( p , q + 2 solve(p,q)=p*q+p*(1-q)*(solve(p,q+2%)+1)+(1-p)*solve(p,q+1.5%) solve(p,q)=p∗q+p∗(1−q)∗(solve(p,q+2 一开始忘了初始条件，当q==100%时，期望等于1/p。

#include
using namespace std;
#define ll long long
const int maxn=110;

double dp[maxn][2];//dp[x][y] q=x+y/2
double p;
double solve(int x,int y){
    if(dp[x][y]>=0.0) return dp[x][y];
    if(x*2+y==200) return 1.0/p;//递归结束条件
    double &res=dp[x][y];
    double q=(1.0*x+1.0*y/2)/100;
    res=p*q;
    if(2*x+y=100)
            res+=p*(1-q)*(solve(100,0)+1.0);
        else
            res+=p*(1-q)*(solve(x+2,y)+1.0);
    }
    x+=1;y+=1;
    if(y>=2){
        x+=1;y-=2;
    }
    if(2*x+y>=200){//
        x=100;y=0;
    }
    res+=(1-p)*(solve(x,y)+1.0);
    return res;
}
void test(){
    for(int a=1;a