把魔杖状态压成「距上次释放的秒数 -> 最大生命值」,再用 cd 单调性二分答案,每次 O(n^2) DP 判可行。
OJ: roj
题目 ID: 1727
难度:提高
标签:动态规划二分答案python
创建: 2026-10-07 18:55
更新: 2026-10-07 18:55
形式化题目
英雄初始生命值
死规则:任意时刻
求最大的正整数 No upper bound.,若 -1。
正解
思路
第一步:把"策略"变成"状态"。 英雄每一秒只有两个动作:不释放、或者在受伤后立刻释放。 释放的收益只取决于当前能量,而能量等于"自从上次释放以来经过的秒数"。 于是做决策需要的全部历史信息就是这两个量:
- 已经释放过几次(只区分
次与 次,因为"上一次释放是什么时候"已经由能量给出); - 当前能量点数
; - 以及该状态下能达到的最大生命值(生命值越大越不会被后续伤害打死,同状态取最大值是安全的)。
记
第二步:从未释放过的那条链只有一个值。 如果一次都没释放,能量就等于当前秒数 never 就够了:
它一旦在某秒受伤后
第三步:转移。 第
| 来源 | 受伤后生命值 | 不释放(能量 |
释放(能量 |
|---|---|---|---|
| 从未释放(能量 |
更新 never(能量继续累积) |
首次释放不受间隔限制,得 |
|
| 已释放过(上一秒能量 |
题面说"相邻两次释放的时间间隔至少有
第四步:对
can_survive(1)为假任何 都不行,输出 -1;can_survive(n+1)为真释放次数至多 次、而单次释放与 无关, 说明 全部可行,输出 No upper bound.;- 否则在
上二分出最大的可行值。
样例推演。 能量 -> 最大生命值,DEAD 表示从未释放的那条链已经死了:
never(受伤后) |
已释放过: |
||
|---|---|---|---|
| 1 | 20 | 10 | |
| 2 | 5 | 5 | |
| 3 | 30 | DEAD | |
| 4 | 4 | DEAD | |
| 5 | 10 | DEAD | |
| 6 | 5 | DEAD | |
| 7 | 20 | DEAD |
第 1 秒就受伤
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 18:58
# update_at: 2026-10-07 18:58
import sys
NEG = -10**18 # 不可达状态的生命值,比任何合法生命值都小
# 已释放过魔杖的状态:能量点数 -> 该状态下的最大生命值(0 表示刚释放完)
type State = dict[int, int]
def can_survive(cd: int, hp: int, a: list[int]) -> bool:
"""施法间隔放宽到 cd 时,英雄能否活过第 n 秒。"""
never = hp # 从未释放:能量点数恒等于当前秒数 i
alive: State = {} # 释放过一次及以上:能量点数 j 即"距上次释放的秒数"
for i, dmg in enumerate(a, 1):
nxt: State = {}
if never > dmg: # 受伤后 hp>0 才来得及释放,否则本秒即死
never -= dmg
nxt[0] = never + 15 * i # 首次释放不受间隔限制,回 15*i 点
else:
never = NEG # 这条链已死亡,之后不再是任何状态的来源
for energy, h in alive.items():
if h <= dmg: # 受伤瞬间 hp<=0,直接死亡
continue
h -= dmg
energy += 1 # 本秒又攒一点能量
nxt[energy] = max(nxt.get(energy, NEG), h) # 不释放
if energy >= cd: # 距上次释放至少 cd 秒才允许再释放
nxt[0] = max(nxt.get(0, NEG), h + 15 * energy)
alive = nxt
all_dead = never == NEG and not alive # 两条来源都断了,之后永远不可达
if all_dead:
break
return never > 0 or any(h > 0 for h in alive.values())
def best_cd(hp: int, a: list[int]) -> int | str:
"""最大的可行施法间隔;-1 表示必死,字符串表示没有上界。"""
if not can_survive(1, hp, a): # cd=1 最宽松,它都不行就必死
return -1
if can_survive(len(a) + 1, hp, a): # cd>n 时至多释放一次,与 cd 无关
return "No upper bound."
lo, hi = 1, len(a) # can_survive 关于 cd 单调不增
while lo < hi:
mid = (lo + hi + 1) // 2
if can_survive(mid, hp, a):
lo = mid
else:
hi = mid - 1
return lo
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, hp = next(data), next(data)
a = [next(data) for _ in range(n)]
print(best_cd(hp, a))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 18:58
* update_at: 2026-10-07 18:58
*/
// 一本通 1727《魔棒》:二分答案 cd + O(n^2) 可行性 DP
//
// 状态:处理完第 i 秒的伤害后,记 (是否释放过魔杖, 当前能量点数) -> 最大生命值。
// · 从未释放:能量点数恒等于 i,只有一条确定的状态链,用一个变量 never 记录;
// · 释放过一次及以上:能量点数 j 就是"距上次释放的秒数",用 dp[j] 记录。
// 首次释放不受间隔限制,此后每次释放都要求 j >= cd,所以两种"释放过"的状态
// 对未来的约束完全相同,可以合并成一个。
// 转移前必须判断 受伤后 hp>0:题面说任何时刻 hp<=0 即死亡,来不及释放回血。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static const ll NEG = -(1LL << 60); // 不可达状态:比任何合法生命值都小
static const int MAXN = 505;
static int n;
static ll hp;
static ll a[MAXN];
static ll dp[MAXN]; // 上一秒:释放过,dp[j] = 能量点数为 j 时的最大生命值
static ll nxt[MAXN]; // 本秒
static ll never; // 从未释放过时的生命值(此链上能量点数恰为当前秒数)
// 判断施法间隔放宽到 cd 时英雄能否活过第 n 秒
static bool can_survive(ll cd) {
never = hp;
for (int j = 0; j <= n; j++) dp[j] = NEG;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= n; j++) nxt[j] = NEG;
// 来源一:从未释放过。能量点数恰为 i,本秒可选择"第一次释放"(无 cd 限制)
if (never > a[i]) {
ll rest = never - a[i]; // 受伤后仍活着,才谈得上释放
never = rest; // 不释放:能量继续累积
nxt[0] = rest + 15LL * i; // 释放:回 15*i 点,能量清零
} else {
never = NEG; // 这条链已经死亡,之后再无来源
}
// 来源二:此前已经释放过,上一秒能量点数 j(本秒变为 j+1)
for (int j = 0; j <= i - 1; j++) {
if (dp[j] <= a[i]) continue; // 受伤瞬间 hp<=0,直接死亡
ll rest = dp[j] - a[i];
ll energy = j + 1; // 本秒又攒了一点能量
if (rest > nxt[energy]) nxt[energy] = rest; // 不释放
if (energy >= cd) { // 距上次释放至少 cd 秒才允许再释放
ll heal = rest + 15LL * energy;
if (heal > nxt[0]) nxt[0] = heal;
}
}
for (int j = 0; j <= n; j++) dp[j] = nxt[j];
}
if (never > 0) return true;
for (int j = 0; j <= n; j++)
if (dp[j] > 0) return true;
return false;
}
int main() {
if (scanf("%d %lld", &n, &hp) != 2) return 0;
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
// cd 越大越难存活,可行区间是前缀 [1, best];cd > n 时至多释放一次,与 cd 无关
if (!can_survive(1)) { printf("-1\n"); return 0; }
if (can_survive(n + 1)) { printf("No upper bound.\n"); return 0; }
ll lo = 1, hi = n, best = 1;
while (lo <= hi) {
ll mid = (lo + hi) / 2;
if (can_survive(mid)) { best = mid; lo = mid + 1; }
else hi = mid - 1;
}
printf("%lld\n", best);
return 0;
}复杂度
设
- 时间:二分
次检查,总计 。 时约为 次转移,实测 main.cpp在 10 个数据点上 单点s(限时 1000 ms)。 - 空间:只保留上一秒与本秒的两行状态,
; main.cpp峰值内存 8.3 MB(限 128 MB)。main.py用字典存"有值的",同样是 状态、常数更小。 - Python 侧:
main.py与 C++ 同为「二分 +状态 DP」,没有降级成枚举策略; 实测最大数据点( )约 0.10 s,即使按更慢的解释器估算也远低于 1 s,无 TLE/MLE 风险。
总结
- 状态里的"次数"可以被"能量"吃掉:释放次数只区分
次与 次就够了, 因为"距上次释放多久"这个更细的信息本来就等于能量点数。 加上"从未释放"那条链的能量恒等于秒数,它甚至退化成一个变量。 - 同状态取最大生命值是正确的贪心:生命值只有下界约束、没有上界, 所以从更高的血出发永远不会更差,这才使 DP 不用记录整份状态集合。
- 死规则决定了转移的判定位置:先扣血、再判
、最后才允许释放; 如果写成"先释放再扣血",小伤害下会得出更乐观、且不符合题面的结果。 - 单调性带来二分:
越大状态集合只会收缩,于是问题从"求最优策略" 变成"判定 + 二分答案", 下 完全够用。 - 数据来源说明:素材源
new_ROJ/problems/1727/里带有数据生成脚本data.py, 10 个测试点由脚本自造(三型输出-1/ 正整数 /No upper bound.全覆盖), 题面本身也属网络重建,出题意图可能与官方原题有偏差;本地std.cpp与本文解法 在 10 个数据点上输出完全一致,可作参照。另需说明:素材源config.json把本题标签 记为"图论"(来源标注为"一本通·高手训练篇·三、图论"),但本题实际是二分答案 + 线性 DP, 与图论无关,本文按题面实际内容标注难度与标签。