The Moon

The Moon

题意：

1.最开始有q=2%的几率掉落物品。

2.你有p%的几率赢的游戏，赢了有q%的几率掉落物品，输了q+1.5%.

3.没掉落q+2%，重复2，3.掉落结束游戏。

问游戏次数期望。

思路： 记忆化搜索。dp[i][j]表示当p=i,q=j时的次数，有两种情况，1种是没赢，1种是赢了但没掉落物品。把p扩大100倍，q扩大200倍。

1.获胜并且没掉落物品

概率=p/100 * （1-q/200）

后继状态：p不变，q=q+2%/200 =q+4   

所以产生的贡献为   p/100 * （1-q/200）* dfs(p/100,min(200,q+4 ))

2.没获胜

概率=1- p/100 

后继状态：p不变，q=q+1.5%/200 =q+3

所以产生的贡献为  (1- p/100 ) *dfs(p/100,min(200,q+3 ))

 

#include<bits/stdc++.h>
using namespace std;
double dp[110][210];
double dfs(int p,int q){
	if(q==200)
		return 100.0/(double)p;
	if(dp[p][q]>-1)
		return dp[p][q];
	return dp[p][q]=1.0+(double)p/100*(1.0-(double)q/200)*dfs(p,min(200,q+4))+(1.0-(double)p/100)*(dfs(p,min(200,q+3)));
} 
int main(){
	int T;
	scanf("%d",&T);
	for(int j=1;j<=T;j++){
		memset(dp,-1,sizeof(dp));
		int p;
		scanf("%d",&p);
		printf("Case %d: %.10lf\n",j,dfs(p,4));
	}
}