algorithm/source/killMonster.cpp at main · jyx-fyh/algorithm · GitHub

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
//
// Created by ButcherX on 23-11-30.
//
#include<iostream>
#include<vector>
#include<cmath>
using std::vector;
double process(int hurt, int restHit, int restBlood)
{
    if(restHit <= 0)
    {
        if(restBlood <= 0)
            return 1;
        else
            return 0;
    }
    if(restBlood <= 0)
        return pow(hurt + 1, restHit);
    double die = 0;
    for(int h = 0; h <= hurt; h++)
    {
        die += process(hurt, restHit - 1, restBlood - h);
    }
    return die;
}

double killMonster(int blood, int hurt, int hitTime)
{
    double all = pow(hurt + 1, hitTime);
    double die = process(hurt, hitTime, blood);
    return die / all;
}
///================================================================
double help(int restHit, int restBlood, int hurt, const vector<vector<double>> &dp)
{
    if(restHit <= 0)
    {
        if(restBlood <= 0)
            return 1;
        else
            return 0;
    }
    if(restBlood <= 0)
        return pow(hurt + 1, restHit);
    return dp[restHit][restBlood];
}
double killMonster1(int blood, int hurt, int hitTime)
{
    vector<vector<double>> dp(hitTime + 1, vector<double>(blood + 1, 0));
    for(int r = 0; r <= hitTime; r++)
    {
        for(int c = 0; c <= blood; c++)
        {
            double die = 0;
            for(int h = 0; h <= hurt; h++)
            {
                die += help(r-1, c-h, hurt, dp);
            }
            dp[r][c] = die;
        }
    }
    return dp[hitTime][blood] / pow(hurt + 1, hitTime);
}
///===================================================
double killMonster2(int blood, int hurt, int hitTime)
{
    vector<vector<double>> dp(hitTime + 1, vector<double>(blood + 1, 0));
    for(int r = 0; r <= hitTime; r++)
    {
        for(int c = 0; c <= blood; c++)
        {
            dp[r][c] = help(r, c-1, hurt, dp) + help(r-1, c, hurt, dp) - help(r-1 ,c-hurt-1, hurt, dp);
        }
    }
    return dp[hitTime][blood] / pow(hurt + 1, hitTime);
}
///====================================================
double help1(int restHit, int restBlood, int hurt, const vector<vector<double>> &dp)
{
    if(restHit <= 0)
    {
        if(restBlood > 0)
            return 1;
        else
            return 0;
    }
    if(restBlood <= 0)
        return 0;
    return dp[restHit][restBlood];
}
double killMonster3(int blood, int hurt, int hitTime)
{
    vector<vector<double>> dp(hitTime + 1, vector<double>(blood + 1, 0));
    for(int r = 0; r <= hitTime; r++)
    {
        for(int c = 0; c <= blood; c++)
        {
            dp[r][c] = help1(r, c-1, hurt, dp) + help1(r-1, c, hurt, dp) - help1(r-1 ,c-hurt-1, hurt, dp);
        }
    }
    return 1 - dp[hitTime][blood] / pow(hurt + 1, hitTime);
}

int main()
{
    std::cout << killMonster1(30, 10, 7) << std::endl;
    std::cout << killMonster3(30, 10, 7) << std::endl;

}