HDU 4870 概率DP

Problem Link

题意

新账号打rank，rank从0开始，打到1000分结束。每场rank增加50的概率为p，否则rank-100。新人用两个信号去打，每次用rank值低的账号，问任意一个账号达到rank1000分，新人要打的期望场数。

解答

参考博客

将分数离散为赢了加1分，输了减2分。用dp[i]表示从i-1分到i分需要打的期望场数。

每次比赛有两种情况，一是p概率赢了加1分，二是(1-p)概率输了减2分。

dp[i]=1*p+(1-p)(1+dp[i-2]+dp[i-1]+dp[i])

期望等于所有情况乘以概率的和。

  • 一场就赢了，则是1*p
  • 一场输了，则需要(1+dp[i-2]+dp[i-1]+dp[i])场才能赢回来。其中1是输了这场，然后从i-3打到i-2,从i-2打到i-1，从i-1打到i分。

化简得

dp[i]=(1+(1-p)*(dp[i-2]+dp[i-1]))/p

dp[1] = 1/p, dp[2] = 1/p/p

注意，因为最低分是0分，所以计算dp[1]和dp[2]的时候公式里填0补充。

用tot记录每一分需要的场数，因为有两个账号，且每次都是用分数低的，所以最后一定是一个账号1000分，另一个账号950分。我们计算两个账号都是1000分需要的场数，即tot*2，然后减去一个950分到1000分的期望场数(dp[20])，即是答案。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<functional>
#define ll long long
using namespace std;
const int mxlen = 25;
double dp[mxlen];

int main(){
    double p;
    while(scanf("%lf",&p)!=EOF){
        dp[1] = 1/p;
        dp[2] = 1/p/p;
        double tot = dp[1]+dp[2];
        for(int i=3;i<=20;i++){
            dp[i] = (1+(1-p)*(dp[i-1]+dp[i-2]))/p;
            tot += dp[i];
        }
        printf("%.6lf\n",2*tot-dp[20]);
    }
    return 0;
}