題干：

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

題目大意：

為了得到一件獎(jiǎng)品而玩一個(gè)游戲（游戲有好多局），得到獎(jiǎng)品后游戲結(jié)束。游戲中的每一局都有p%的概率會(huì)贏（p是個(gè)給定的常數(shù)），初始中獎(jiǎng)率q=2，如果這一局贏了就抽獎(jiǎng)，沒抽到就q+2，然后繼續(xù)游戲的下一局；如果這一局輸了就q+1.5。問玩的游戲局?jǐn)?shù)的期望。中獎(jiǎng)率最高為100%，也就是說如果這一局贏了且沒抽到獎(jiǎng)，那q=min(q+2,100%) 如果這一局輸了，那q=min(q+1.5,100%)。

解題報(bào)告：

設(shè)dp[i]代表當(dāng)前狀態(tài)的中獎(jiǎng)率為 i% 時(shí)，得到獎(jiǎng)品的期望天數(shù)。

因?yàn)橐阎獱顟B(tài)是終點(diǎn)的狀態(tài)，所以倒著dp。考慮初始化，dp[100]=1/p。（當(dāng)然，注意p上來要先除以100，因?yàn)樗o的是p%）

又因?yàn)榇藭r(shí)中獎(jiǎng)的概率是100%，也就是說贏即可以中獎(jiǎng)，也就是轉(zhuǎn)化成贏的期望局?jǐn)?shù)，贏一局的概率是p，顯然這符合幾何概型，所以期望局?jǐn)?shù)=1/p。

然后轉(zhuǎn)移就是? ?dp[i]=? ? ? ? ? p *? ? ? ?[ q*1+(1-q)*(dp[i+2]+1)] + (1-p) * (dp[i+1.5] + 1)?

分別代表：? ? ? ?? ?贏游戲的前提下? ?( 中獎(jiǎng)? ? ?沒中獎(jiǎng)? ? ? ? ?)? ??? ? ? ? 沒贏游戲

然后化簡(jiǎn)一下公式就可以了。注意這里因?yàn)橛?.5不能放到狀態(tài)中，所以直接都*2，這樣狀態(tài)變成0~200.這樣就方便轉(zhuǎn)移了。

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

?

總結(jié)

以上是生活随笔為你收集整理的【HDU - 6558】The Moon（期望dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。