【HDU - 6558】The Moon（期望dp）

题干：

Random Six is a FPS game made by VBI(Various Bug Institution). There is a gift named "Beta Pack". Mr. K wants to get a beta pack. Here is the rule.
Step 0. Let initial chance rate qq = 2%.
Step 1. Player plays a round of the game with winning rate pp.
Step 2. If the player wins, then will go to Step 3 else go to Step 4.
Step 3. Player gets a beta pack with probability qq. If he doesn’t get it, let qq = min(100%, qq + 2%) and he will go to Step 1.
Step 4. Let qq = min(100%, qq + 1.5%) and goto Step 1.
Mr. K has winning rate pp% , he wants to know what’s the expected number of rounds before he needs to play.

Input

The first line contains testcase number TT (TT ≤ 100). For each testcase the first line contains an integer pp (1 ≤ pp ≤ 100).

Output

For each testcase print Case ii : and then print the answer in one line, with absolute or relative error not exceeding 106106.

Sample Input

2
50
100

Sample Output

Case 1: 12.9933758002
Case 2: 8.5431270393

题目大意：

为了得到一件奖品而玩一个游戏（游戏有好多局），得到奖品后游戏结束。游戏中的每一局都有p%的概率会赢（p是个给定的常数），初始中奖率q=2，如果这一局赢了就抽奖，没抽到就q+2，然后继续游戏的下一局；如果这一局输了就q+1.5。问玩的游戏局数的期望。中奖率最高为100%，也就是说如果这一局赢了且没抽到奖，那q=min(q+2,100%) 如果这一局输了，那q=min(q+1.5,100%)。

解题报告：

设dp[i]代表当前状态的中奖率为 i% 时，得到奖品的期望天数。

因为已知状态是终点的状态，所以倒着dp。考虑初始化，dp[100]=1/p。（当然，注意p上来要先除以100，因为他给的是p%）

又因为此时中奖的概率是100%，也就是说赢即可以中奖，也就是转化成赢的期望局数，赢一局的概率是p，显然这符合几何概型，所以期望局数=1/p。

然后转移就是   dp[i]=          p *       [ q*1+(1-q)*(dp[i+2]+1)] + (1-p) * (dp[i+1.5] + 1) 

分别代表：          赢游戏的前提下   ( 中奖     没中奖         )            没赢游戏

然后化简一下公式就可以了。注意这里因为有0.5不能放到状态中，所以直接都*2，这样状态变成0~200.这样就方便转移了。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
double dp[255],p;
int main()
{
	int T,iCase=0;
	cin>>T;
	while(T--) {
		scanf("%lf",&p); p/=100;
		double gp = 1.0/p;
		dp[200] = gp;
		for(int i = 199; i>=1; i--) {
			dp[i] = p*((1-i/200.0)*dp[min(i+4,200)]+1) + (1-p)*(dp[min(i+3,200)]+1);
		}
		printf("Case %d: %.10f\n",++iCase,dp[4]);
	}


	return 0 ;
}