引言
今日心血来潮，想起了一道之前没有解决的算法题，但我现已近一年没碰过算法了。
根底问题
相信咱们都玩过奇特宝物和相似游戏，本文咱们一起考虑奇特宝物和相似游戏对战的一系列简化模型，并研讨其中的概率论问题。假如你之前没有学过概率dp和希望dp，那么本文能够教你一点概率dp和希望dp的套路，并提升一点点写小模仿的才干。
- 我方和BOSS轮番开释技术，技术能够形成损伤、给自身和队友（假如允许多打多）回血、添加特点等。
- 特点包含进犯、防护、特攻、特防、血量、速度等。开释技术先后顺序由速度决议；技术损伤由威力、我方进犯、对手防护、技术系别、对手系别（水、火、草……）等要素决议，并且会乘一个随机系数添加可玩性。
- 技术有运用次数约束，名为PP值，还能够吃药补PP值。
- ……
一道算法题，要考虑上述一切要素就太复杂了，咱们先提炼一个精简的模型，来编写一道简略的概率论题目。根底问题如下：BOSS有x滴血，我一局打BOSS掉y滴血，BOSS有p的概率回z滴血，有1-p的概率进犯我。我均匀需求几局能打败BOSS？假定：（1）我血量无限。（2）血量不能超过血量上限。（3）我先手，且打赢BOSS那局应该算1局而非0.5局。（3）y <= x。
全希望公式、全概率公式和希望dp、概率dp
全概率公式：P(B) = sum(P(A[i]) * P(B | A[i]))
全希望公式：E(B) = sum(P(A[i]) * E(B | A[i]))
这两个公式思想是一致的，便是将问题划分为若干个互斥事情，并分别求条件概率和条件希望。在算法竞赛中，条件概率和条件希望往往能够用dp来描绘，dp的意义一般为“从初始状况到终态”的希望步数or概率。而dp的各个维度既能将问题划分为若干互斥事情，也是对当时局势的一种描绘。
有时咱们写出的状况搬运方程存在循环依靠，此刻能够尝试消除循环依靠，比方：设中间变量。但假如做不到，咱们往往需求将其建模为方程组才干求解，不过大多数状况下希望dp和概率dp的方程组都是线性方程组。
经过其他算法题，了解了上述套路后，本文你就不需求再看了，由于本文涉及的技巧都太过明显了，只剩下了完成上的难度。假如没有了解，能够以本文为例帮助了解上述套路。
作者：hans774882968以及hans774882968以及hans774882968
本文52pojie：www.52pojie.cn/thread-1766…
本文juejin：/post/721596…
本文CSDN：blog.csdn.net/hans7748829…
根底问题：希望dp做法
设dp[i]为BOSS从i滴血的初始局势到被打败均匀需求几局。由全希望公式：
dp[0] = 0
dp[1~y] = 1
dp[y+1] = 1 + p*dp[min(z+1,x)] + (1-p)*dp[1]
dp[y+2] = 1 + p*dp[min(z+2,x)] + (1-p)*dp[2]
# 即
dp[i] = 1 + p*dp[min(i-y+z,x)] + (1-p)*dp[i-y]
这个dp有依靠关系，线性时刻复杂度的做法似乎不好想，那就用线性方程组解吧！我选择用numpy来解线性方程组，假如import失利，需求pip install numpy进行装置。具体见代码。
根底问题：brute force，或许说是蒙特卡洛模仿
蒙特卡洛模仿的做法主要是用于对拍。由于我手头没有数据，所以我以为对拍程序和算法输出结果差异较小，即为两者完成均正确。在brute force做法中，为了完成方便，我用了一个小技巧：把退出条件设为cur_blood > y，退出后只需求1局或0局即可打败BOSS。
也能够将我放技术和BOSS放技术的动作拆解开来。这个写法在“扩展2”及以后一切扩展问题中都是必需的。
根底问题：代码
brute force函数名base_bf。
import random
import numpy as np
def base_dp(x: int, y: int, z: int, p: float):
b = np.array([[1 if i else 0] for i in range(x + 1)])
a = [[0] * (x + 1) for _ in range(x + 1)]
for i in range(x + 1):
a[i][i] = 1
for i in range(y + 1, x + 1):
a[i][min(i - y + z, x)] -= p
a[i][i - y] += p - 1
a = np.array(a)
ans = np.linalg.solve(a, b)
return ans[x][0]
def base_bf(x: int, y: int, z: int, p: float, trys=1000000):
def bf(x: int, y: int, z: int, p: float):
ret = 0
cur_blood = x
while cur_blood > y:
ret += 1
rv = random.random()
if rv < p:
cur_blood = min(cur_blood - y + z, x)
else:
cur_blood -= y
# 剩1～y滴血时，1局可打败
return ret + (1 if cur_blood > 0 else 0)
tot = 0
for _ in range(trys):
tot += bf(x, y, z, p)
return tot / trys
print(base_dp(4, 1, 2, 0.25)) # 6.037037037037038
print(base_bf(4, 1, 2, 0.25))
print(base_dp(80, 14, 22, 0.2)) # 8.216744626007252
print(base_bf(80, 14, 22, 0.2))
扩展1：考虑我方血量
BOSS有x1滴血，我有x2滴血，BOSS一局打我掉y1滴血，我一局打BOSS掉y2滴血，BOSS有p的概率回z滴血，有1-p的概率进犯我。赢界说为：BOSS血量小于等于0且我方血量大于0。我赢的概率是多少？假定：（1）血量不能超过血量上限。（2）我先手。（3）y2 <= x1, y1 <= x2。
PS：本来还想问：我在成功的状况下的希望局数。但想来原理是差不多的，就先不写了。
扩展1：2维的概率dp
能够用(BOSS血量, 我的血量)来描绘一个局势。设dp[i][j]为当时局势BOSS有i滴血，我有j滴血，到“赢”的各个状况，即局势(0, j > 0)的概率之和。由全概率公式：
dp[0~x1][0] = 0
dp[0][1~x2] = 1
# 值得留意的是，这儿抽出了我方再进犯一次就成功（必胜）的局势，这是针对“扩展1”的特殊性的做法，能够简化代码完成，但后续不能再运用这个技巧。
dp[1~y2][1~x2] = 1
dp[i][j] = p*dp[min(i-y2+z,x1)][j] + (1-p)*dp[i-y2][j-y1], i = y2+1~x1, j = 1~x2
这儿需求越界判别，假如j <= y1，则dp[i-y2][j-y1]应改为取0。
依旧是用矩阵完成，这儿的完成难度会比上面大一些。我运用的技巧是，将上面给出的dp公式进行编号，dp[0~x1][0] = 0为第0～x1号公式，依此类推，于是能够保护一个expression_count变量。有expression_count后，咱们正常枚举BOSS血量和自己的血量，并初始化矩阵即可。别的，能够引进一个pos函数，来指出某个局势对应的矩阵中的方位，以减小编码难度：
# boss, me
def pos(i, j):
if i < 0 or i > x1 or j < 0 or j > x2:
raise Exception("越界！")
return i * (x2 + 1) + j
扩展1：brute force
仍然是一道小模仿，但难度更大了。学习上一题的主意，我把退出条件仅设定为BOSS必败，并在循环中识别我失利的场景。
也能够将我放技术和BOSS放技术的动作拆解开来。这个写法在后续一切的扩展问题中都是有必要的。
扩展1：代码
brute force函数名i_may_lose_bf。在测试数据中发现了一些规则。
import random
import numpy as np
# boss血量，我血量，boss进犯，我进犯，boss回血技术回血量，boss发起回血技术概率
def i_may_lose_dp(x1: int, x2: int, y1: int, y2: int, z: int, p: float):
mat_size = (x1 + 1) * (x2 + 1)
# boss, me
def pos(i, j):
if i < 0 or i > x1 or j < 0 or j > x2:
raise Exception("越界！")
return i * (x2 + 1) + j
b = [[0] for _ in range(mat_size)]
for i in range(x1 + 1, x1 + 1 + x2 + y2 * x2):
b[i][0] = 1
b = np.array(b)
a = [[0] * mat_size for _ in range(mat_size)]
expression_count = 0
for i in range(x1 + 1):
a[expression_count][pos(i, 0)] = 1
expression_count += 1
for i in range(1, x2 + 1):
a[expression_count][pos(0, i)] = 1
expression_count += 1
for i in range(1, y2 + 1):
for j in range(1, x2 + 1):
a[expression_count][pos(i, j)] = 1
expression_count += 1
assert expression_count == x1 + 1 + x2 + y2 * x2
for i in range(y2 + 1, x1 + 1):
for j in range(1, x2 + 1):
a[expression_count][pos(i, j)] = 1
a[expression_count][pos(min(i - y2 + z, x1), j)] -= p
if j > y1:
a[expression_count][pos(i - y2, j - y1)] += p - 1
expression_count += 1
assert expression_count == mat_size
a = np.array(a)
ans = np.linalg.solve(a, b)
return ans[mat_size - 1][0]
def i_may_lose_bf(
x1: int,
x2: int,
y1: int,
y2: int,
z: int,
p: float,
trys=1000000
):
def bf(x1: int, x2: int, y1: int, y2: int, z: int, p: float):
ret = 0
boss_blood, my_blood = x1, x2
while boss_blood > y2:
ret += 1
rv = random.random()
if rv < p:
boss_blood = min(boss_blood - y2 + z, x1)
else:
boss_blood -= y2
my_blood -= y1
if my_blood <= 0:
return -1, False
# boss剩1～y2滴血时，1局后我必胜
return ret + (1 if boss_blood > 0 else 0), True
tot, win_count = 0, 0
for _ in range(trys):
step, is_win = bf(x1, x2, y1, y2, z, p)
if is_win:
tot += step
win_count += 1
return tot / win_count if win_count else -114514, win_count / trys
cases = [
# (4, 5, 1, 1, 2, 0.25), # 0.80859375
# (4, 6, 1, 1, 2, 0.3), # 0.8673489999999998
# (17, 18, 3, 4, 5, 0.2), # 0.9998172160000002
# (17, 17, 3, 3, 5, 0.25), # 0.31640625
# (26, 27, 5, 5, 9, 0.3), # 0.5282199999999998
(26, 17, 2, 3, 2, 0.3), # 1
(26, 17, 2, 3, 3, 0.3), # 1
(26, 17, 2, 3, 4, 0.3), # 0.2552983299999999
(26, 17, 2, 3, 5, 0.3), # 0.08235429999999996
(26, 17, 2, 3, 6, 0.3), # 0.08235429999999996
# (24, 24, 5, 5, 5, 0.3), # 1
# (24, 24, 5, 5, 6, 0.3), # 0.6516999999999998
# (24, 24, 5, 5, 7, 0.3), # 0.3429999999999999
# (24, 24, 5, 5, 9, 0.3), # 0.3429999999999999
# (24, 24, 5, 5, 10, 0.3), # 0.3429999999999999
# (24, 24, 5, 5, 25, 0.3), # 0.3429999999999999
# (23, 22, 4, 4, 4, 0.3), # 1
# (23, 22, 4, 4, 5, 0.3), # 0.5282199999999998
# (23, 22, 4, 4, 6, 0.3), # 0.24009999999999992
# (23, 22, 4, 4, 7, 0.3), # 0.24009999999999992
# (23, 22, 4, 4, 20, 0.3), # 0.24009999999999992
# (23, 20, 4, 4, 0, 0.3), # 0.8319300000000001
# (23, 20, 4, 4, 1, 0.3), # 0.8319300000000001
# (23, 20, 4, 4, 2, 0.3), # 0.579825
# (23, 20, 4, 4, 3, 0.3), # 0.3529305
# (23, 20, 4, 4, 4, 0.3), # 0
# (23, 15, 4, 4, 0, 0.25), # 0.3671875
# (23, 15, 4, 4, 1, 0.25), # 0.16943359375
# (23, 15, 4, 4, 2, 0.25), # 0.070556640625
# (23, 15, 4, 4, 3, 0.25), # 0.003505706787109375
# (23, 15, 4, 4, 4, 0.25), # 0
]
for c in cases:
ans1 = i_may_lose_dp(*c)
ans2 = i_may_lose_bf(*c)
print(ans1 - ans2[1], ans1, ans2)
扩展2：两边都能进犯或回血
这个问题有对称性了。做法和扩展1差不多，也比扩展3简略，但时刻关系我先搁置了，由咱们补全代码～
扩展3：我方能运用加进犯技术且有次数约束，对方能无限次运用回血技术
BOSS和我分别有boss_blood, my_blood滴血，BOSS和我的进犯、防护分别为boss_attack, my_attack, boss_defense, my_defense，BOSS回血量为boss_add_blood，回血技术运用概率为boss_add_blood_probability，我运用加进犯技术的概率为my_add_attack_probability，我运用加进犯技术的次数上限为my_add_attack_limit。我打BOSS的血量为my_power = max((k + 1) * my_attack - boss_defense, 0)，k表明我当时的进犯等级，在这个问题中简化为运用加进犯技术的次数，取值0~my_add_attack_limit。BOSS打我的血量为boss_power = max(boss_attack - my_defense, 0)。赢界说为：BOSS血量小于等于0且我方血量大于0。我赢的概率是多少？假定：（1）两边血量不能超过血量上限。（2）我先手，且打赢BOSS那局应该算1局而非0.5局。（3）boss_power > 0且my_biggest_power = (my_add_attack_limit + 1) * my_attack - boss_defense大于0，这条约束保证战役能完毕。
扩展3：3维dp
做法和“扩展1”相似，咱们需求引进一个新的维度，表明初始状况下我现已运用的加进犯技术的次数。更具体地说，dp界说扩展为：dp[i][j][k]表明boss初始血量为i，我初始血量为j，我初始状况现已运用的加进犯次数为k的局势下我赢的概率，这儿“赢”依旧是指抵达一系列局势的概率之和。答案为dp[boss_blood][my_blood][0]。
边界条件：
dp[0~boss_blood][0][0~my_add_attack_limit] = 0dp[0][1~my_blood][0~my_add_attack_limit] = 1
值得留意的是，扩展1将一种必胜局势抽出，作为边界条件，以简化代码完成。但咱们在此只给出了真正的边界条件，不再专门取出一切的1局后必胜条件，由于假如问题继续扩展，那么人工枚举一切的必胜条件几乎是不可能的。
状况搬运方程：dp[i][j][k] = (1-my_add_attack_probability*boss_add_blood_probability*dp[min(i-my_power+boss_add_blood,boss_blood)][j][k] + (1-my_add_attack_probability)*(1-boss_add_blood_probability)*dp[i-my_power][j-boss_power][k] + my_add_attack_probability*boss_add_blood_probability*dp[i][min(j+boss_add_blood,boss_blood)][k+1] + my_add_attack_probability*(1-boss_add_blood_probability)*dp[i][j-boss_power][k+1]，其主意便是简略枚举一切的技术运用状况。这个状况搬运方程仅仅一种直观描绘，实际上，我打BOSS和BOSS打我的状况都要留意断定血量，血量需求取到非正数时，dp值应改为取常量1或0。dp值取常量1表明b[expression_count]要进行相应添加，dp值取常量0表明对a的操作越过。别的，还需求判别我运用加进犯技术的次数是否现已到达上限，假如到达了运用加进犯技术次数上限，那么进犯的概率应该是1。在代码完成中，为了简略，我把k < my_add_attack_limit和k == my_add_attack_limit的状况拆为2个循环。放在一个循环中，并界说一个变量my_actual_add_attack_probability = my_add_attack_probability if k < my_add_attack_limit else 0的完成方式应该也是可行的。
TODO：找一个和dp状况数相同数量级的做法，假如找不到，也能够退而求其次，找一个稀疏矩阵的算法。
相关代码如下：
def i_can_add_attack_dp(
boss_blood: int,
my_blood: int,
boss_attack: int,
my_attack: int,
boss_defense: int,
my_defense: int,
boss_add_blood: int,
boss_add_blood_probability: float,
my_add_attack_probability: float,
my_add_attack_limit: int
):
mat_size = (boss_blood + 1) * (my_blood + 1) * (my_add_attack_limit + 1)
# boss_blood, my_blood, my_add_attack_num
def pos(i: int, j: int, k: int):
if i < 0 or i > boss_blood or j < 0 or j > my_blood or k < 0 or k > my_add_attack_limit:
raise Exception("越界！(%s, %s, %s)" % (i, j, k))
return i * (my_blood + 1) * (my_add_attack_limit + 1) + \
j * (my_add_attack_limit + 1) + k
a = [[0] * mat_size for _ in range(mat_size)]
b = [[0] for _ in range(mat_size)]
expression_count = 0
for i in range(boss_blood + 1):
for k in range(my_add_attack_limit + 1):
a[expression_count][pos(i, 0, k)] = 1
expression_count += 1
for j in range(1, my_blood + 1):
for k in range(my_add_attack_limit + 1):
a[expression_count][pos(0, j, k)] = 1
b[expression_count][0] = 1
expression_count += 1
for i in range(1, boss_blood + 1):
for j in range(1, my_blood + 1):
for k in range(my_add_attack_limit):
my_power = max((k + 1) * my_attack - boss_defense, 0)
boss_power = max(boss_attack - my_defense, 0)
a[expression_count][pos(i, j, k)] = 1
# 我进犯，BOSS加血
if my_power >= i:
b[expression_count][0] += (
1 - my_add_attack_probability) * boss_add_blood_probability
else:
a[expression_count][pos(min(i - my_power + boss_add_blood, boss_blood), j, k)] -= (
1 - my_add_attack_probability) * boss_add_blood_probability
# 我进犯，BOSS进犯
if my_power >= i:
b[expression_count][0] += (1 - my_add_attack_probability) * \
(1 - boss_add_blood_probability)
elif boss_power < j:
a[expression_count][pos(i - my_power, j - boss_power, k)] -= (
1 - my_add_attack_probability) * (1 - boss_add_blood_probability)
# 我加进犯，BOSS加血
a[expression_count][pos(min(i + boss_add_blood, boss_blood), j, k + 1)
] -= my_add_attack_probability * boss_add_blood_probability
# 我加进犯，BOSS进犯
if boss_power < j:
a[expression_count][pos(
i, j - boss_power, k + 1)] -= my_add_attack_probability * (1 - boss_add_blood_probability)
expression_count += 1
for i in range(1, boss_blood + 1):
for j in range(1, my_blood + 1):
my_power = max((my_add_attack_limit + 1) *
my_attack - boss_defense, 0)
boss_power = max(boss_attack - my_defense, 0)
a[expression_count][pos(i, j, my_add_attack_limit)] = 1
# 我进犯，BOSS加血
if my_power >= i:
b[expression_count][0] += boss_add_blood_probability
else:
a[expression_count][pos(min(i - my_power + boss_add_blood, boss_blood),
j, my_add_attack_limit)] -= boss_add_blood_probability
# 我进犯，BOSS进犯
if my_power >= i:
b[expression_count][0] += 1 - boss_add_blood_probability
elif boss_power < j:
a[expression_count][pos(
i - my_power, j - boss_power, my_add_attack_limit)] -= 1 - boss_add_blood_probability
expression_count += 1
assert expression_count == mat_size
a = np.array(a)
b = np.array(b)
ans = np.linalg.solve(a, b)
return ans[pos(boss_blood, my_blood, 0)][0]
扩展3：brute force
需求保护的状况多了一个：我当时的进犯等级my_cur_attack_level。值得留意的是，咱们有必要拆解我方和BOSS开释技术的动作。
咱们引进了my_actual_add_attack_probability变量my_actual_add_attack_probability = my_add_attack_probability if my_cur_attack_level < my_add_attack_limit else 0，这样后续代码就只需求人工枚举两边开释技术的一切可能状况，简化了代码完成。
相关代码如下（PS：这段代码应该能够用面向对象来规范一下，但我懒得做了……）：
def i_can_add_attack_bf(
boss_blood: int,
my_blood: int,
boss_attack: int,
my_attack: int,
boss_defense: int,
my_defense: int,
boss_add_blood: int,
boss_add_blood_probability: float,
my_add_attack_probability: float,
my_add_attack_limit: int,
trys=1000000
):
assert boss_attack > my_defense # 暂不支撑BOSS打不动我的状况
assert 0 <= boss_add_blood_probability and boss_add_blood_probability <= 1
assert 0 <= my_add_attack_probability and my_add_attack_probability < 1
def bf(
boss_blood: int,
my_blood: int,
boss_attack: int,
my_attack: int,
boss_defense: int,
my_defense: int,
boss_add_blood: int,
boss_add_blood_probability: float,
my_add_attack_probability: float,
my_add_attack_limit: int
):
ret = 0
boss_cur_blood, my_cur_blood, my_cur_attack_level = boss_blood, my_blood, 0
while True:
ret += 1
pivot_boss_skill = random.random()
pivot_my_skill = random.random()
# 引进 my_actual_add_attack_probability
# ，这样后续代码就能够简化为两边开释状况的人工枚举，即若干个if块
my_actual_add_attack_probability = my_add_attack_probability if my_cur_attack_level < my_add_attack_limit else 0
boss_skill_is_attack = pivot_boss_skill >= boss_add_blood_probability
boss_skill_is_add_blood = pivot_boss_skill < boss_add_blood_probability
my_skill_is_attack = pivot_my_skill >= my_actual_add_attack_probability
my_skill_is_add_attack = pivot_my_skill < my_actual_add_attack_probability
if my_skill_is_attack and boss_skill_is_add_blood:
my_power = max((my_cur_attack_level + 1) *
my_attack - boss_defense, 0)
if my_power >= boss_cur_blood:
return ret, True
boss_cur_blood = min(
boss_cur_blood - my_power + boss_add_blood,
boss_blood
)
if my_skill_is_attack and boss_skill_is_attack:
my_power = max((my_cur_attack_level + 1) *
my_attack - boss_defense, 0)
if my_power >= boss_cur_blood:
return ret, True
boss_cur_blood -= my_power
boss_power = max(boss_attack - my_defense, 0)
if boss_power >= my_cur_blood:
return -1, False
my_cur_blood -= boss_power
if my_skill_is_add_attack and boss_skill_is_add_blood:
my_cur_attack_level += 1
boss_cur_blood = min(
boss_cur_blood + boss_add_blood,
boss_blood
)
if my_skill_is_add_attack and boss_skill_is_attack:
my_cur_attack_level += 1
boss_power = max(boss_attack - my_defense, 0)
if boss_power >= my_cur_blood:
return -1, False
my_cur_blood -= boss_power
tot, win_count = 0, 0
for _ in range(trys):
step, is_win = bf(boss_blood,
my_blood,
boss_attack,
my_attack,
boss_defense,
my_defense,
boss_add_blood,
boss_add_blood_probability,
my_add_attack_probability,
my_add_attack_limit)
if is_win:
tot += step
win_count += 1
return tot / win_count if win_count else -114514, win_count / trys
扩展3：主动生成测试用例
人工测试用例，由“扩展1”的测试用例（由于“扩展1”是“扩展3”的子问题）和一些随意写的测试用例组成。为了方便测试代码正确性，咱们写一段引进主动生成测试用例的代码。这段代码的主体是一个无限循环，取随机数直到满意我的条件：（1）战役能够较快完毕。（2）矩阵的大小不能太大。
别的，为什么失利条件设得比较宽松delta >= 0.001呢？由于我发现蒙特卡洛模仿，只做1e6次的状况下得到的成功次数差异能够到达1000，且限于计算资源，模仿次数不能设太大。再说一个小tips，假如发现差值总是正数或总是负数，并且概率差值有时能到达0.01，这说明你的代码有一些纤细的错误。
def gen_cases(case_count=3):
cases = []
for _ in range(case_count):
while True:
boss_blood = random.randint(1, 20)
my_blood = random.randint(1, 20)
boss_attack = random.randint(1, 10)
my_attack = random.randint(1, 10)
boss_defense = random.randint(1, 10)
my_defense = random.randint(1, 10)
boss_add_blood = random.randint(1, 15)
boss_add_blood_probability = random.random() / 1.2
my_add_attack_probability = random.random() / 1.2
my_add_attack_limit = random.randint(0, 3)
my_biggest_power = (my_add_attack_limit + 1) * \
my_attack - boss_defense
boss_power = max(boss_attack - my_defense, 0)
mat_size = (boss_blood + 1) * (my_blood + 1) * \
(my_add_attack_limit + 1)
if my_biggest_power > 0 and boss_blood / \
my_biggest_power < 5 and boss_power > 0 and my_blood / boss_power < 5 and mat_size <= 1000:
cases.append((
boss_blood,
my_blood,
boss_attack,
my_attack,
boss_defense,
my_defense,
boss_add_blood,
boss_add_blood_probability,
my_add_attack_probability,
my_add_attack_limit
))
break
return cases
def run_auto_cases(case_count=3):
cases = gen_cases(case_count)
for c in cases:
ans1 = i_can_add_attack_dp(*c)
ans2 = i_can_add_attack_bf(*c)
delta = abs(ans1 - ans2[1])
if delta >= 0.001:
print('[run_auto_cases] 代码在这个用例下可能有问题qwq', c)
else:
print('[run_auto_cases]', c)
print(ans1 - ans2[1], ans1, ans2[1])
run_auto_cases()
扩展3：完整代码
import random
import numpy as np
# boss_blood my_blood boss_attack my_attack boss_defense my_defense boss_add_blood
# boss_add_blood_probability my_add_attack_probability my_add_attack_limit
# boss血量，我血量，boss进犯力，我进犯力，boss防护力，我防护力，boss回血技术回血量，boss发起回血技术概率，我运用加进犯技术概率，我加进犯次数约束
# dp[i][j][k] boss初始血量 我初始血量 我初始状况现已运用的加进犯次数，答案 = dp[boss_blood][my_blood][0]
# dp[0~boss_blood][0][0~my_add_attack_limit] = 0
# dp[0][1~my_blood][0~my_add_attack_limit] = 1
# dp[i][j][k] = (1-my_add_attack_probability)*boss_add_blood_probability*dp[min(i-my_power+boss_add_blood,boss_blood)][j][k] +
# (1-my_add_attack_probability)*(1-boss_add_blood_probability)*dp[i-my_power][j-boss_power][k] +
# my_add_attack_probability*boss_add_blood_probability*dp[i][min(j+boss_add_blood,boss_blood)][k+1] +
# my_add_attack_probability*(1-boss_add_blood_probability)*dp[i][j-boss_power][k+1]
# my_power = max((k + 1) * my_attack - boss_defense, 0)
# boss_power = max(boss_attack - my_defense, 0)
# 我打BOSS和BOSS打我的状况都要留意断定血量，血量需求取到非正数时，dp值应改为取常量1或0，dp值取常量1表明b[expression_count]要进行相应添加，dp值取常量0表明对a的操作越过
def i_can_add_attack_dp(
boss_blood: int,
my_blood: int,
boss_attack: int,
my_attack: int,
boss_defense: int,
my_defense: int,
boss_add_blood: int,
boss_add_blood_probability: float,
my_add_attack_probability: float,
my_add_attack_limit: int
):
mat_size = (boss_blood + 1) * (my_blood + 1) * (my_add_attack_limit + 1)
# boss_blood, my_blood, my_add_attack_num
def pos(i: int, j: int, k: int):
if i < 0 or i > boss_blood or j < 0 or j > my_blood or k < 0 or k > my_add_attack_limit:
raise Exception("越界！(%s, %s, %s)" % (i, j, k))
return i * (my_blood + 1) * (my_add_attack_limit + 1) + \
j * (my_add_attack_limit + 1) + k
a = [[0] * mat_size for _ in range(mat_size)]
b = [[0] for _ in range(mat_size)]
expression_count = 0
for i in range(boss_blood + 1):
for k in range(my_add_attack_limit + 1):
a[expression_count][pos(i, 0, k)] = 1
expression_count += 1
for j in range(1, my_blood + 1):
for k in range(my_add_attack_limit + 1):
a[expression_count][pos(0, j, k)] = 1
b[expression_count][0] = 1
expression_count += 1
for i in range(1, boss_blood + 1):
for j in range(1, my_blood + 1):
for k in range(my_add_attack_limit):
my_power = max((k + 1) * my_attack - boss_defense, 0)
boss_power = max(boss_attack - my_defense, 0)
a[expression_count][pos(i, j, k)] = 1
# 我进犯，BOSS加血
if my_power >= i:
b[expression_count][0] += (
1 - my_add_attack_probability) * boss_add_blood_probability
else:
a[expression_count][pos(min(i - my_power + boss_add_blood, boss_blood), j, k)] -= (
1 - my_add_attack_probability) * boss_add_blood_probability
# 我进犯，BOSS进犯
if my_power >= i:
b[expression_count][0] += (1 - my_add_attack_probability) * \
(1 - boss_add_blood_probability)
elif boss_power < j:
a[expression_count][pos(i - my_power, j - boss_power, k)] -= (
1 - my_add_attack_probability) * (1 - boss_add_blood_probability)
# 我加进犯，BOSS加血
a[expression_count][pos(min(i + boss_add_blood, boss_blood), j, k + 1)
] -= my_add_attack_probability * boss_add_blood_probability
# 我加进犯，BOSS进犯
if boss_power < j:
a[expression_count][pos(
i, j - boss_power, k + 1)] -= my_add_attack_probability * (1 - boss_add_blood_probability)
expression_count += 1
for i in range(1, boss_blood + 1):
for j in range(1, my_blood + 1):
my_power = max((my_add_attack_limit + 1) *
my_attack - boss_defense, 0)
boss_power = max(boss_attack - my_defense, 0)
a[expression_count][pos(i, j, my_add_attack_limit)] = 1
# 我进犯，BOSS加血
if my_power >= i:
b[expression_count][0] += boss_add_blood_probability
else:
a[expression_count][pos(min(i - my_power + boss_add_blood, boss_blood),
j, my_add_attack_limit)] -= boss_add_blood_probability
# 我进犯，BOSS进犯
if my_power >= i:
b[expression_count][0] += 1 - boss_add_blood_probability
elif boss_power < j:
a[expression_count][pos(
i - my_power, j - boss_power, my_add_attack_limit)] -= 1 - boss_add_blood_probability
expression_count += 1
assert expression_count == mat_size
a = np.array(a)
b = np.array(b)
ans = np.linalg.solve(a, b)
return ans[pos(boss_blood, my_blood, 0)][0]
def i_can_add_attack_bf(
boss_blood: int,
my_blood: int,
boss_attack: int,
my_attack: int,
boss_defense: int,
my_defense: int,
boss_add_blood: int,
boss_add_blood_probability: float,
my_add_attack_probability: float,
my_add_attack_limit: int,
trys=1000000
):
assert boss_attack > my_defense # 暂不支撑BOSS打不动我的状况
assert 0 <= boss_add_blood_probability and boss_add_blood_probability <= 1
assert 0 <= my_add_attack_probability and my_add_attack_probability < 1
def bf(
boss_blood: int,
my_blood: int,
boss_attack: int,
my_attack: int,
boss_defense: int,
my_defense: int,
boss_add_blood: int,
boss_add_blood_probability: float,
my_add_attack_probability: float,
my_add_attack_limit: int
):
ret = 0
boss_cur_blood, my_cur_blood, my_cur_attack_level = boss_blood, my_blood, 0
while True:
ret += 1
pivot_boss_skill = random.random()
pivot_my_skill = random.random()
# 引进 my_actual_add_attack_probability
# ，这样后续代码就能够简化为两边开释状况的人工枚举，即若干个if块
my_actual_add_attack_probability = my_add_attack_probability if my_cur_attack_level < my_add_attack_limit else 0
boss_skill_is_attack = pivot_boss_skill >= boss_add_blood_probability
boss_skill_is_add_blood = pivot_boss_skill < boss_add_blood_probability
my_skill_is_attack = pivot_my_skill >= my_actual_add_attack_probability
my_skill_is_add_attack = pivot_my_skill < my_actual_add_attack_probability
if my_skill_is_attack and boss_skill_is_add_blood:
my_power = max((my_cur_attack_level + 1) *
my_attack - boss_defense, 0)
if my_power >= boss_cur_blood:
return ret, True
boss_cur_blood = min(
boss_cur_blood - my_power + boss_add_blood,
boss_blood
)
if my_skill_is_attack and boss_skill_is_attack:
my_power = max((my_cur_attack_level + 1) *
my_attack - boss_defense, 0)
if my_power >= boss_cur_blood:
return ret, True
boss_cur_blood -= my_power
boss_power = max(boss_attack - my_defense, 0)
if boss_power >= my_cur_blood:
return -1, False
my_cur_blood -= boss_power
if my_skill_is_add_attack and boss_skill_is_add_blood:
my_cur_attack_level += 1
boss_cur_blood = min(
boss_cur_blood + boss_add_blood,
boss_blood
)
if my_skill_is_add_attack and boss_skill_is_attack:
my_cur_attack_level += 1
boss_power = max(boss_attack - my_defense, 0)
if boss_power >= my_cur_blood:
return -1, False
my_cur_blood -= boss_power
tot, win_count = 0, 0
for _ in range(trys):
step, is_win = bf(boss_blood,
my_blood,
boss_attack,
my_attack,
boss_defense,
my_defense,
boss_add_blood,
boss_add_blood_probability,
my_add_attack_probability,
my_add_attack_limit)
if is_win:
tot += step
win_count += 1
return tot / win_count if win_count else -114514, win_count / trys
def gen_cases(case_count=3):
cases = []
for _ in range(case_count):
while True:
boss_blood = random.randint(1, 20)
my_blood = random.randint(1, 20)
boss_attack = random.randint(1, 10)
my_attack = random.randint(1, 10)
boss_defense = random.randint(1, 10)
my_defense = random.randint(1, 10)
boss_add_blood = random.randint(1, 15)
boss_add_blood_probability = random.random() / 1.2
my_add_attack_probability = random.random() / 1.2
my_add_attack_limit = random.randint(0, 3)
my_biggest_power = (my_add_attack_limit + 1) * \
my_attack - boss_defense
boss_power = max(boss_attack - my_defense, 0)
mat_size = (boss_blood + 1) * (my_blood + 1) * \
(my_add_attack_limit + 1)
if my_biggest_power > 0 and boss_blood / \
my_biggest_power < 5 and boss_power > 0 and my_blood / boss_power < 5 and mat_size <= 1000:
cases.append((
boss_blood,
my_blood,
boss_attack,
my_attack,
boss_defense,
my_defense,
boss_add_blood,
boss_add_blood_probability,
my_add_attack_probability,
my_add_attack_limit
))
break
return cases
def run_auto_cases(case_count=3):
cases = gen_cases(case_count)
for c in cases:
ans1 = i_can_add_attack_dp(*c)
ans2 = i_can_add_attack_bf(*c)
delta = abs(ans1 - ans2[1])
if delta >= 0.001:
print('[run_auto_cases] 代码在这个用例下可能有问题qwq', c)
else:
print('[run_auto_cases]', c)
print(ans1 - ans2[1], ans1, ans2[1])
# 扩展1的case
no_add_attack_cases = [
# (4, 5, 1, 1, 0, 0, 2, 0.25, 0, 0), # 0.80859375
# (4, 6, 1, 1, 0, 0, 2, 0.3, 0, 0), # 0.8673489999999998
# (17, 18, 3, 4, 0, 0, 5, 0.2, 0, 0), # 0.9998172160000002
# (17, 17, 3, 3, 0, 0, 5, 0.25, 0, 0), # 0.31640625
# (26, 27, 5, 5, 0, 0, 9, 0.3, 0, 0), # 0.5282199999999998
# (26, 17, 2, 3, 0, 0, 2, 0.3, 0, 0), # 1
# (26, 17, 2, 3, 0, 0, 3, 0.3, 0, 0), # 1
# (26, 17, 2, 3, 0, 0, 4, 0.3, 0, 0), # 0.2552983299999999
# (26, 17, 2, 3, 0, 0, 5, 0.3, 0, 0), # 0.08235429999999996
# (26, 17, 2, 3, 0, 0, 6, 0.3, 0, 0), # 0.08235429999999996
# (24, 24, 5, 5, 0, 0, 5, 0.3, 0, 0), # 1
# (24, 24, 5, 5, 0, 0, 6, 0.3, 0, 0), # 0.6516999999999998
# (24, 24, 5, 5, 0, 0, 7, 0.3, 0, 0), # 0.3429999999999999
# (24, 24, 5, 5, 0, 0, 9, 0.3, 0, 0), # 0.3429999999999999
# (24, 24, 5, 5, 0, 0, 10, 0.3, 0, 0), # 0.3429999999999999
# (24, 24, 5, 5, 0, 0, 25, 0.3, 0, 0), # 0.3429999999999999
# (23, 22, 4, 4, 0, 0, 4, 0.3, 0, 0), # 1
# (23, 22, 4, 4, 0, 0, 5, 0.3, 0, 0), # 0.5282199999999998
# (23, 22, 4, 4, 0, 0, 6, 0.3, 0, 0), # 0.24009999999999992
# (23, 22, 4, 4, 0, 0, 7, 0.3, 0, 0), # 0.24009999999999992
# (23, 22, 4, 4, 0, 0, 20, 0.3, 0, 0), # 0.24009999999999992
# (23, 20, 4, 4, 0, 0, 0, 0.3, 0, 0), # 0.8319300000000001
# (23, 20, 4, 4, 0, 0, 1, 0.3, 0, 0), # 0.8319300000000001
# (23, 20, 4, 4, 0, 0, 2, 0.3, 0, 0), # 0.579825
# (23, 20, 4, 4, 0, 0, 3, 0.3, 0, 0), # 0.3529305
# (23, 20, 4, 4, 0, 0, 4, 0.3, 0, 0), # 0
# (23, 15, 4, 4, 0, 0, 0, 0.25, 0, 0), # 0.3671875
# (23, 15, 4, 4, 0, 0, 1, 0.25, 0, 0), # 0.16943359375
# (23, 15, 4, 4, 0, 0, 2, 0.25, 0, 0), # 0.070556640625
# (23, 15, 4, 4, 0, 0, 3, 0.25, 0, 0), # 0.003505706787109375
# (23, 15, 4, 4, 0, 0, 4, 0.25, 0, 0), # 0
]
cases = [
*no_add_attack_cases,
# (4, 5, 1, 1, 0, 0, 2, 0.25, 0.25, 3), # 0.9160377010889875
# (4, 6, 1, 1, 0, 0, 2, 0.3, 0.25, 3), # 0.9741987084147316
# (17, 18, 3, 4, 0, 0, 5, 0.2, 0.25, 3), # 0.9820515464729096
# (17, 17, 3, 3, 0, 0, 5, 0.25, 0.25, 3), # 0.8115670869690697
# (26, 27, 5, 5, 0, 0, 9, 0.3, 0.25, 3), # 0.873849609228737
# (26, 17, 2, 3, 0, 0, 2, 0.3, 0.2, 3), # 0.9905333909547174
# (26, 17, 2, 3, 0, 0, 3, 0.3, 0.2, 3), # 0.9777544970640041
# (26, 17, 2, 3, 0, 0, 4, 0.3, 0.2, 3), # 0.9147414027044304
# (26, 17, 2, 3, 0, 0, 5, 0.3, 0.2, 3), # 0.8731776837795042
# (26, 17, 2, 3, 0, 0, 6, 0.3, 0.2, 3), # 0.8492809049470756
# (24, 24, 5, 5, 0, 0, 5, 0.3, 0.25, 3), # 0.9183074507949731
# (24, 24, 5, 5, 0, 0, 6, 0.3, 0.25, 3), # 0.8585987923823502
# (24, 24, 5, 5, 0, 0, 7, 0.3, 0.25, 3), # 0.7740757521611915
# (24, 24, 5, 5, 0, 0, 9, 0.3, 0.25, 3), # 0.7433988933602607
# (24, 24, 5, 5, 0, 0, 10, 0.3, 0.25, 3), # 0.7409449791377299
# (24, 24, 5, 5, 0, 0, 25, 0.3, 0.25, 3), # 0.6575242627019245
# (23, 22, 4, 4, 0, 0, 4, 0.3, 0.2, 3), # 0.9443943496217228
# (23, 22, 4, 4, 0, 0, 5, 0.3, 0.2, 3), # 0.8574007848491916
# (23, 22, 4, 4, 0, 0, 6, 0.3, 0.2, 3), # 0.7658891690144051
# (23, 22, 4, 4, 0, 0, 7, 0.3, 0.2, 3), # 0.7475453781164894
# (23, 22, 4, 4, 0, 0, 20, 0.3, 0.2, 3), # 0.6679427026235988
# (23, 20, 4, 4, 0, 0, 0, 0.3, 0.25, 3), # 0.8686731676567078
# (23, 20, 4, 4, 0, 0, 1, 0.3, 0.25, 3), # 0.8562376017170137
# (23, 20, 4, 4, 0, 0, 2, 0.3, 0.25, 3), # 0.771857783579355
# (23, 20, 4, 4, 0, 0, 3, 0.3, 0.25, 3), # 0.7163414966132311
# (23, 20, 4, 4, 0, 0, 4, 0.3, 0.25, 3), # 0.6691316566228978
# (23, 15, 4, 4, 0, 0, 0, 0.25, 0.2, 3), # 0.5077913500000001
# (23, 15, 4, 4, 0, 0, 1, 0.25, 0.2, 3), # 0.4285612324000001
# (23, 15, 4, 4, 0, 0, 2, 0.25, 0.2, 3), # 0.35735150696320006
# (23, 15, 4, 4, 0, 0, 3, 0.25, 0.2, 3), # 0.3222425538737369
# (23, 15, 4, 4, 0, 0, 4, 0.25, 0.2, 3), # 0.30972575195312513
# (12, 9, 6, 4, 10, 4, 11, 0.642597, 0.077409, 3), # 0.05168324414398858
# (18, 11, 10, 7, 5, 5, 3, 0.319059, 0.506039, 3), # 0.45683775982637675
# (2, 7, 8, 3, 7, 6, 8, 0.152426, 0.575946, 2), # 0.7198123697734008
# (6, 4, 6, 10, 7, 3, 7, 0.029775, 0.589464, 2), # 0.4342016554147815
# (3, 16, 10, 5, 10, 2, 7, 0.570169, 0.287427, 2), # 0.2696812367978718
# (1, 16, 9, 2, 5, 4, 5, 0.533026, 0.123434, 3), # 0.23279906085426308
# (5, 13, 9, 8, 9, 1, 11, 0.341245, 0.322049, 3), # 0.411064579885941
# (12, 7, 6, 9, 1, 2, 10, 0.587649, 0.30710, 1), # 0.9389672281289208
]
for c in cases:
ans1 = i_can_add_attack_dp(*c)
ans2 = i_can_add_attack_bf(*c)
print(ans1 - ans2[1], ans1, ans2)
delta = abs(ans1 - ans2[1])
if delta >= 0.001:
print('[manual_cases] 代码在这个用例下可能有问题qwq', c)
run_auto_cases()
