HDU - 6558 D - The Moon （概率dp）

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 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

題意：

一個人的初始中獎率為q = 2%，他要玩若干局遊戲，每輪遊戲獲勝的概率都為p，每輪遊戲有以下三種情況：

（1）遊戲獲勝，可以抽一次獎，如果獲獎則遊戲結束。

（2）遊戲獲勝，可以抽一次獎，如果沒有獲獎則中獎概率q += 2%

（3）遊戲輸了，q += 1.5%

問中獎前玩遊戲的期望輪數。

思路：

對上面三種情況分析，可以得出每種情況的概率：

（1）概率為p * q，遊戲結束

（2）概率為p * (1 - q)，q += 2%

（3）概率為(1 - p)，q += 1.5%

考慮概率dp，用dp[i][j]表示在第 i 輪遊戲結束後 q = j 的概率，不難發現，它只可以從第i - 1輪的兩個狀態q = j - 0.02和q = j - 0.015轉移過來（分別對應情況2和情況3），q = j - 0.02 轉移過來的概率就是 p * (1 - q)，q = j - 0.015轉移過來的概率是(1 - p)，那麼轉移方程就可以寫出來了：

推到這裡我們發現，dp[i][j]表示的是第 i 輪遊戲結束後 q = j 的概率啊，那怎麼求出輪數的期望呢？

考慮第 i 輪結束時q = j，第i + 1輪結束遊戲，（i + 1）是輪數，dp[i][j] * p * j是得到當前狀態的概率，那麼輪數的期望值就要加上(i + 1) * dp[i][j] * p * j

所以答案是什麼呢，答案就是把所有狀態的期望都加起來，第一層迴圈列舉遊戲輪數，第二層迴圈列舉q值，當某一輪中所有q值對應的期望加起來都 < eps，就break

有幾個需要注意的地方：

（1）狀態轉移方程第一維沒有什麼用啊，快去掉

（2）q值是小數，狀態裡要乘1000

（3）所有的q都是由q - 0.02和q = 0.015轉移過來的嗎？答：不是。q = 1可以由[1 - 0.02, 1]裡的任何一個數轉移過來，還可以從[1 - 0.015, 1]裡的任何一個數轉移過來，並且這兩種轉移方式相互獨立，因為第一個對應情況2，第二個對應情況3。

（4）eps取1e-6就足夠了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-6;
const int N = 1e3 + 10;

double dp[N];

int main() {
    int t, kcase = 0;
    double p;
    scanf("%d", &t);
    while(t--) {
        scanf("%lf", &p);
        p /= 100.0;
        for(int i = 0; i < N; ++i)
            dp[i] = 0.0;
        dp[20] = 1.0;
        double ans = 0.0;
        for(int i = 1; ; ++i) {
            double tmp = 0.0;
            for(int j = 1000; j >= 20; --j) {
                if(j == 1000) {
                    dp[j] = dp[j] * (1.0 - p);
                    for(int k = 980; k < 1000; ++k)
                        dp[j] += 1.0 * dp[k] * p * (1.0 - 1.0 * k / 1000.0);
                    for(int k = 985; k < 1000; ++k)
                        dp[j] += 1.0 * dp[k] * (1.0 - p);
                }
                else
                    dp[j] = 1.0 * dp[j - 20] * p * (1.0 - 1.0 * (j - 20) / 1000.0) + 1.0 * dp[j - 15] * (1.0 - p);
                tmp += 1.0 * (i + 1) * dp[j] * p * j / 1000.0;
            }
            ans += 1.0 * tmp;
            if(tmp < eps) break;
        }
        ans += 0.02 * p;
        printf("Case %d: %.7f\n", ++kcase, ans);
    }
	return 0;
}