THE MOON（概率dp）

题目描述
The Moon card shows alarge, 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.

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

输出
For each testcase print Case i : and then print the answer in one line, with absolute or relative error not exceeding 10-6.

样例输入
2
50
100

样例输出
Case 1: 12.9933758002
Case 2: 8.5431270393

思路
用概率dp的想法来解这题，从 100% 是逆推至 2%的情况，因为存在+1.5%的情况状态，所以单位采用千分位，转移方程为

dp[i]=p*((i/1000.0)+(1-i/1000.0)*(1+dp[min(i+20,1000)]));
dp[i]+=(1-p)*(1+dp[min(i+15,1000)]);

代码实现

#include<bits/stdc++.h>

using namespace std;
double p;
int T;
double dp[1005];
int main()
{
    scanf("%d",&T);
    for(int id=1;id<=T;id++)
    {
        scanf("%lf",&p);
        memset(dp,0,sizeof(dp));
        p/=100;
        dp[1000]=1/p;
        for(int i=999;i>=20;i--){
            dp[i]=p*((i/1000.0)+(1-i/1000.0)*(1+dp[min(i+20,1000)]));
            dp[i]+=(1-p)*(1+dp[min(i+15,1000)]);
        }
        printf("Case %d: ",id);
        cout<<fixed<<setprecision(10)<<dp[20]<<endl;
    }
    return 0;
}