题意:
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.
题解:dp[i][j]表示 q为i,p为j时的期望次数,因为有一个1.5的存在,所以我们的q都乘10进行计算
dp[q][p]=1+1.0*p/100*(1-1.0*q/1000)*dp[min(q+20,1000)][p]+(100.0-p)/100*dp[min(q+15,1000)][p]
初始dp[1000][i]=100/i
#include<bits/stdc++.h>
using namespace std;
double dp[1010][110];
double dfs(int q,int p)
{
if(dp[q][p]!=-1)return dp[q][p];
dp[q][p]=1+1.0*p/100*(1-1.0*q/1000)*dfs(min(q+20,1000),p)+(100.0-p)/100*dfs(min(q+15,1000),p);
return dp[q][p];
}
int main()
{
for(int i=1;i<=1000;i++)
{
for(int j=1;j<=100;j++)
dp[i][j]=-1;
}
for(int i=1;i<=100;i++)
dp[1000][i]=100.0/i;
int T,p;
int nn=1;
scanf("%d",&T);
while(T--)
{
scanf("%d",&p);
printf("Case %d: %.10f\n",nn++,dfs(20,p));
}
return 0;
}