(迫真oi部)银梦雄志传

说明
在之后的战斗中，石川•麻里奈的生命值可能高于初始值。
一个关卡只能被选择一次。

提示：活着才有输出

哦哦哦哦哦哦哦哦哦哦

看懂了，那麼遊戲可以在哪裡玩到呢?

分成两组，第一组di小于ri（打完增加hp），第二组di大于ri（打完减少hp），先选第一组的，前面尽量加血，大概是这样吗

经典的动态规划问题，可以使用动态规划的思路来解决。
首先构建一个状态转移方程来描述问题。假设dp[i][j]表示在剩余生命值为j的情况下，能否通过前i个关卡。得到以下的状态转移方程：
dp[i][j]=dp[i-1][max{j+r_i, d_i}] (j>=d_i)
其中，r_i和d_i分别表示第i个关卡的恢复生命值和消耗生命值。
接下来，使用动态规划的方法来求解这个问题。具体地，从后往前遍历所有的关卡，依次计算每个关卡的状态转移。最后，我们可以得到dp[n][H]，其中n是关卡的总数，H是初始的生命值。如果dp[n][H]为True，则说明可以通过所有的关卡；否则，说明无法通过所有的关卡。

又根据题目描述，我们可以得知n=5，H=2，并且每个关卡的消耗和恢复生命值分别为：
关卡1：消耗1，恢复2
关卡2：消耗2，恢复4
关卡3：消耗1，恢复2
关卡4：消耗2，恢复0
关卡5：消耗2，恢复0
由此列出状态转移表，由表可知生命值为2时可通过所有关卡，而顺序答案是1、3、2、5、4。
解决这个问题时，我们首先需要确定哪些关卡可以安全通过，即消耗的生命值小于等于恢复的生命值。可以使用贪心算法来解决这个问题。将关卡按照消耗的生命值从大到小排序，然后遍历这些关卡，如果消耗的生命值小于等于恢复的生命值，我们就将其加入到通关顺序中，并将生命值更新为恢复后的生命值。如果遍历结束后还有剩余的生命值，说明存在解决方案；否则，说明无解。

定义一个二维数组 dp[i][j]，表示前 i 个关卡，当前生命值为 j 的情况下是否能够通过游戏。
状态转移方程为：
dp[i][j] = any(dp[k][max(l, k+m)] for l in range(min(j + r_i - m*di_i, h), max(-1, min(j - di_i)))))
其中，k 表示已经选择的关卡的数量，m 表示还未选择的关卡中最小的 di_i，r_i 表示还未选择的关卡中最大的 ri。
初始化条件为：dp[0][j] = True，dp[i][0] = False，其他 dp[i][j] = None。
最终的答案为 dp[n][h]。

代码如下:
def findOrder(n, h):
if n == 1: return [0]
# 初始化二维数组
dp = [[None]*(h+1) for _ in range(n+1)]
# 初始化条件
for i in range(n+1): dp[i][0] = False
for j in range(h+1): dp[0][j] = True
# 状态转移
for i in range(1, n+1):
for j in range(1, h+1):
if dp[i][j]: continue
# 枚举未选择的关卡数量 k
for k in range(i):
if dp[k][max(l, k)]: # l = j + ri - ki * di
m = min((ki+1)*di for ki in range(k, i))
r_max = max([ri-m*mi for mi, ri in zip(*[enumerate(di+j for di in dp)])))
if j >= r_max: break # 若 r_max <= m*mi, 则无解
dp[i][j] = any([dp[k][min((ki+m)*di + r_max, h)] for k in range(i-1)])
# 输出答案
if dp[n][h]: return [i for i in range(n)]
else: return [-1]

除了题干毫无inm要素的纯粹数学讨论，想必是银教育家提升学生学习兴趣的诡计吧（无关心）