HDU 6558 The Moon(概率dp)

The Moon

Problem Description
The Moon card shows a large, full moon in the night’s sky, positioned between two large towers. The Moon is a symbol of intuition, dreams, and the unconscious. The light of the moon is dim, compared to the sun, and only vaguely illuminates the path to higher consciousness which winds between the two towers.

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 q = 2%.
Step 1. Player plays a round of the game with winning rate p.
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 q. If he doesn’t get it, let q = min(100%, q + 2%) and he will go to Step 1.
Step 4. Let q = min(100%, q + 1.5%) and goto Step 1.
Mr. K has winning rate p% , he wants to know what’s the expected number of rounds before he needs to play.

Input
The first line contains testcase number T (T ≤ 100). For each testcase the first line contains an integer p (1 ≤ p ≤ 100).

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

Sample Input

2
50
100

Sample Output

Case 1: 12.9933758002
Case 2: 8.5431270393

题意
一个初始中奖率q=2,每次玩一局游戏，如果游戏赢了就抽奖，没抽到就q+2,然后继续玩游戏，如果游戏输了就q+1.5。问玩的游戏局数的期望，并且中奖率最高为100%

题解
给出初始的中奖概率p=2%
输入的是每局游戏的获胜概率p
这样的话我们用$dp[i]$表示获奖概率为$i$时的期望
因为$q$最高为$100\%$，所以初始状态为$dp[100]$，但是因为如果游戏输了的话是$p+1.5$，而数组的下标是不能用小数的，所以我们整体扩大２倍，初始状态设为$dp[200]$
因为当$q=100\%$的时候，我们只要游戏赢了就结束，即n局游戏前n-1局都是输只有第n局赢，所以满足几何分布，根据几何分布期望公式,$dp[200]=\frac{1}{p}$
接下来是状态转移方程
$dp[q]=p\cdot (1-q)\cdot dp[min(q+4,200)]+(1-p)dp[min(q+3,200)]+1$
其中１是当前局，$p\cdot (1-q)\cdot dp[min(q+4,200)]$为游戏获胜但是未中奖的期望，$(1-p)dp[min(q+3,200)]$为游戏失败的期望，三者和即为概率为q时的期望

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <cmath>

using namespace std;
#define me(x,y) memset(x,y,sizeof x)
#define MIN(x,y) x < y ? x : y
#define MAX(x,y) x > y ? x : y

typedef long long ll;
typedef unsigned long long ull;

const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const double eps = 1e-09;
const double PI = acos(-1.0);

int main(){
    int t,ca=1;cin>>t;
    while(t--){
        double p;scanf("%lf",&p);
        p/=100;
        double dp[240];
        memset(dp,0,sizeof dp);
        dp[200]=1/p;
        for(int i=199; i >= 4; --i){
            dp[i]=1+p*(1-1.0*i/200)*dp[min(i+4,200)];
            dp[i]+=(1-p)*(dp[min(i+3,200)]);
        }
        printf("Case %d: %.10lf\n",ca++,dp[4]);
    }
}

/*
 
*/