魔棒

GitHub跳转原题关系图返回列表

把魔杖状态压成「距上次释放的秒数 -> 最大生命值」,再用 cd 单调性二分答案,每次 O(n^2) DP 判可行。

OJ: roj

题目 ID: 1727

难度:提高

标签:动态规划二分答案python

创建: 2026-10-07 18:55

更新: 2026-10-07 18:55

形式化题目

英雄初始生命值 hphp(无上限),在接下来 nn 秒内第 ii 秒受到伤害 aia_i (aia_i 为负表示回血)。魔杖初始能量 00,英雄每受到一次伤害就积攒 1 点能量; 在受到伤害之后,允许立刻把当前能量全部释放,回血 15×(当前能量)15 \times (\text{当前能量}), 并把能量清零。相邻两次释放的时间间隔必须至少为 cdcd。

死规则:任意时刻 hp≤0hp \le 0 即死亡。注意受伤的瞬间 hp≤0hp \le 0 就已经死亡, 来不及用这次伤害换来的能量回血,所以每次转移都要求"受伤后仍 hp>0hp > 0"。

求最大的正整数 cdcd 使得英雄能活到第 nn 秒结束;若可以任意大输出 No upper bound.,若 cd=1cd=1 也活不下来输出 -1。

正解

思路

第一步:把"策略"变成"状态"。 英雄每一秒只有两个动作:不释放、或者在受伤后立刻释放。 释放的收益只取决于当前能量,而能量等于"自从上次释放以来经过的秒数"。 于是做决策需要的全部历史信息就是这两个量:

  • 已经释放过几次(只区分 00 次与 ≥1\ge 1 次,因为"上一次释放是什么时候"已经由能量给出);
  • 当前能量点数 jj;
  • 以及该状态下能达到的最大生命值(生命值越大越不会被后续伤害打死,同状态取最大值是安全的)。

记 dpi(j)dp_i(j) 为"第 ii 秒受伤后、已经释放过至少一次、当前能量为 jj"时的最大生命值。

第二步:从未释放过的那条链只有一个值。 如果一次都没释放,能量就等于当前秒数 ii, 没有第二种可能,所以不必为它开数组,用一个变量 never 就够了:

neveri=hp−(a1+a2+⋯+ai). \texttt{never}_i = hp - (a_1 + a_2 + \cdots + a_i).

它一旦在某秒受伤后 ≤0\le 0 就整条链死掉,此后不再产生任何状态。

第三步:转移。 第 ii 秒先扣血 aia_i,要求扣完仍然 >0>0;然后决定是否释放。 释放时回血 15j15j、能量清零,两个来源的写法完全一致:

来源 受伤后生命值 不释放(能量 j+1j+1) 释放(能量 00,需 j+1≥cdj+1 \ge cd)
从未释放(能量 =i=i) never−ai\texttt{never} - a_i 更新 never(能量继续累积) 首次释放不受间隔限制,得 +15i+15i
已释放过(上一秒能量 jj) dp(j)−aidp(j) - a_i dp′(j+1)←max⁡(⋅)dp'(j+1) \gets \max(\cdot) dp′(0)←max⁡(⋅)dp'(0) \gets \max(\cdot) 加 15(j+1)15(j+1)

题面说"相邻两次释放的时间间隔至少有 cdcd 秒"。设上次在第 t1t_1 秒释放, 那么第 t2t_2 秒释放时能量恰好是 t2−t1t_2 - t_1,所以这个约束就是能量 j≥cdj \ge cd (首次释放之前没有释放过,"间隔"无从谈起,不受 cdcd 限制)。样例可以验证这条读法: cd=2cd = 2 时最优策略在第 1,4,61,4,6 秒释放,间隔是 33 与 22,答案确实是 22; 把"至少 cdcd 秒"误读成"至少 cd+1cd+1 秒"会算出答案 11,与样例冲突。

第四步:对 cdcd 二分。 cdcd 越大,释放的机会越少,可达状态集合只会变小, 所以"能存活"关于 cdcd 是单调的(真值的集合是前缀 [1,cdmax⁡][1, cd_{\max}]):

  • can_survive(1) 为假 ⇒\Rightarrow 任何 cdcd 都不行,输出 -1;
  • can_survive(n+1) 为真 ⇒\Rightarrow 释放次数至多 11 次、而单次释放与 cdcd 无关, 说明 cd≥n+1cd \ge n+1 全部可行,输出 No upper bound.;
  • 否则在 [1,n][1, n] 上二分出最大的可行值。

样例推演。 n=7,hp=30,a=(20,5,30,4,10,5,20)n=7, hp=30, a = (20,5,30,4,10,5,20),取 cd=2cd=2。 下表的"已释放过"列格式为 能量 -> 最大生命值,DEAD 表示从未释放的那条链已经死了:

ii aia_i never(受伤后) 已释放过:j→hpj \to hp
1 20 10 0→250 \to 25
2 5 5 0→35,  1→200 \to 35,\; 1 \to 20
3 30 DEAD 1→51 \to 5
4 4 DEAD 0→31,  2→10 \to 31,\; 2 \to 1
5 10 DEAD 1→211 \to 21
6 5 DEAD 0→46,  2→160 \to 46,\; 2 \to 16
7 20 DEAD 1→261 \to 26

第 1 秒就受伤 ⇒\Rightarrow 能量 1,此时可以选择首次释放:10+15=2510 + 15 = 25。 第 3 秒的 30 点伤害会清空大部分状态,只剩"能量 1、生命 5"这一支; 它撑到第 7 秒结束仍有 26 点血,所以 cd=2cd = 2 可行。 换成 cd=3cd = 3 后,第 5 秒时能量最多到 2 还没到 cdcd、又吃 10 点伤害, 所有分支都死在第 5 秒,故 cd=3cd = 3 不可行,答案是 22。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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;
}

复杂度

设 f(cd)f(cd) 为一次可行性检查的代价:内层对每个秒数 ii 枚举能量 j≤ij \le i, 共 O(n2)O(n^2) 次转移,每次 O(1)O(1)。

  • 时间:二分 O(log⁡n)O(\log n) 次检查,总计 O(n2log⁡n)O(n^2 \log n)。n=500n = 500 时约为 5002×9≈2.25×106500^2 \times 9 \approx 2.25 \times 10^6 次转移,实测 main.cpp 在 10 个数据点上 单点 ≤0.011\le 0.011 s(限时 1000 ms)。
  • 空间:只保留上一秒与本秒的两行状态,O(n)O(n);main.cpp 峰值内存 8.3 MB(限 128 MB)。 main.py 用字典存"有值的 jj",同样是 O(n)O(n) 状态、常数更小。
  • Python 侧:main.py 与 C++ 同为「二分 + O(n2)O(n^2) 状态 DP」,没有降级成枚举策略; 实测最大数据点(n=500n=500)约 0.10 s,即使按更慢的解释器估算也远低于 1 s,无 TLE/MLE 风险。

总结

  • 状态里的"次数"可以被"能量"吃掉:释放次数只区分 00 次与 ≥1\ge 1 次就够了, 因为"距上次释放多久"这个更细的信息本来就等于能量点数。 加上"从未释放"那条链的能量恒等于秒数,它甚至退化成一个变量。
  • 同状态取最大生命值是正确的贪心:生命值只有下界约束、没有上界, 所以从更高的血出发永远不会更差,这才使 DP 不用记录整份状态集合。
  • 死规则决定了转移的判定位置:先扣血、再判 hp>0hp > 0、最后才允许释放; 如果写成"先释放再扣血",小伤害下会得出更乐观、且不符合题面的结果。
  • 单调性带来二分:cdcd 越大状态集合只会收缩,于是问题从"求最优策略" 变成"判定 + 二分答案",n≤500n \le 500 下 O(n2log⁡n)O(n^2\log n) 完全够用。
  • 数据来源说明:素材源 new_ROJ/problems/1727/ 里带有数据生成脚本 data.py, 10 个测试点由脚本自造(三型输出 -1 / 正整数 / No upper bound. 全覆盖), 题面本身也属网络重建,出题意图可能与官方原题有偏差;本地 std.cpp 与本文解法 在 10 个数据点上输出完全一致,可作参照。另需说明:素材源 config.json 把本题标签 记为"图论"(来源标注为"一本通·高手训练篇·三、图论"),但本题实际是二分答案 + 线性 DP, 与图论无关,本文按题面实际内容标注难度与标签。