第45届ICPC亚洲网上区域赛模拟赛-D

第45届ICPC亚洲网上区域赛模拟赛-D

十一月 01, 2020

Pokemon Ultra Sun

  • 题意

两只pokemon对战 A有hp1血量B有hp2血量

每回合A有p的概率对B造成w的伤害

或者B有1-p的概率对A造成w的伤害

当有一方血量低于或等于0时结束

问对战回合(轮数)的期望值

  • 题解

首先需要知道求期望的一般公式 $Exp=∑_{i=0}^{n}i×p_i$

对于此题轮数的期望值= 1轮结束的概率×1+2轮结束的概率×2+….n轮结束的概率×n

例如样例：

hp1=3，hp2=1，w=1

p=0.8

第一轮结束的局面有(3,0),对应概率为0.8

第二轮结束的局面有(2,0),对应概率为0.2×0.8

第三轮结束的局面有(1,0),(0,1) 对应概率为0.2×0.2×0.8 和 0.2×0.2×0.2

所以 $Exp=1×0.8+2×0.2×0.8+3×(0.2×0.2×0.8 和 0.2×0.2×0.2)$

上图对于局面状态(概率)的转移就已经显而易见了

设计dp(i,j)表示到达A剩余i血 B剩余j血的局面概率

更新完dp后根据期望公式直接求得答案

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
#define P pair<ll,ll>
const int Max=2e5+5;
const int Mod=1e9+7;
const int inf=0x3f3f3f3f;

/*

3
3 1 1
0.5
*/
double dp[3005][3005];
int main(){
    //Turnoff;
    //int q;cin>>q;
    int q;scanf("%d",&q);
    while(q--){
        int hp1,hp2,w;
        double p;
        scanf("%d %d %d %lf",&hp1,&hp2,&w,&p);
        //printf("%f\n",p);
        memset(dp,0,sizeof dp);
        dp[hp1][hp2]=1;
        int A=ceil(1.0*hp1/w),B=ceil(1.0*hp2/w);
        for(int i=0;i<=A;i++){
            for(int j=0;j<=B;j++){
                if(j&&hp1-i*w>0&&hp2-(j-1)*w>0)dp[max(0,hp1-i*w)][max(0,hp2-j*w)]+=dp[hp1-i*w][hp2-(j-1)*w]*p;
                if(i&&hp1-(i-1)*w>0&&hp2-j*w>0)dp[max(0,hp1-i*w)][max(0,hp2-j*w)]+=dp[hp1-(i-1)*w][hp2-j*w]*(1-p);
                //printf("(%d,%d) <-(%d,%d) : %f\n",max(0,hp1-i*w),max(0,hp2-j*w),max(0,hp1-i*w),max(0,hp2-(j-1)*w),dp[max(0,hp1-i*w)][max(0,hp2-(j-1)*w)]*p);
                //printf("(%d,%d) <-(%d,%d) : %f\n",max(0,hp1-i*w),max(0,hp2-j*w),max(0,hp1-(i-1)*w),max(0,hp2-j*w),dp[max(0,hp1-(i-1)*w)][max(0,hp2-j*w)]*(1-p));
            }
        }
        double ans=0;
        for(int i=1;i<=hp1;i++){
            if((hp1-i)%w)continue;
            int round=(hp1-i)/w+B;
            ans+=dp[i][0]*round;
        }
        for(int j=1;j<=hp2;j++){
            if((hp2-j)%w)continue;
            int round=(hp2-j)/w+A;
            ans+=dp[0][j]*round;
        }
        printf("%.6f\n",ans);
    }
}