【ccpc2018吉林D题】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

 

题意：

1.起初物品掉落率q=2%;

2.玩家进行一次游戏，有p的概率获胜。

3.如果获胜了，有q的概率掉落一个叫Beta Pack的物品。如果获胜，q+=2%;否则，q+=1.5%。

重复2和3。

求得到一个物品 进行游戏场次的期望。

思路：

先设dp[i][j]表示p=i/100（非整除，下同）,q=j/200时所需要进行的场次（因为小数不能作下标，所以把p扩大100倍，把q扩大200倍记录下来），这个dp数组是用来记忆化搜索的。

dfs(p,q)是用来求p/100,q/200时所需要进行的场次

那么dfs的时候只需要根据题意：

现状态: 获胜率p，掉落率q（扩大后的）

如果掉落率已经100%了，即q==200，那么ans=100/p（这是dfs的边界）；

否则，ans=1（本场游戏）+获胜并且没掉落物品的情况+没获胜的情况  （如果获胜并且掉落物品的话，游戏就结束了，就没有后继情况了）

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<iostream>
#include<cstdio>
using namespace std;
int t,p;
double dp[110][210];
double dfs(int p,int q){
    if(q==200)return 100.0/(double)p;
    if(dp[p][q]>-0.5)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(){
    scanf("%d",&t);
    for(int i=0;i<=100;++i)
        for(int j=0;j<=200;++j)
            dp[i][j]=-1;
    for(int ca=1;ca<=t;++ca){
        scanf("%d",&p);
        printf("Case %d: %.10f\n",ca,dfs(p,4));
    }
    return 0;
}