# 力场护盾：题解

## 解法比较

出题人解法用时间与位置的二维差分还原伤害，统计启用时可被保护的建筑，再用空间前缀和与单调队列求每个时刻的一次最大保护量。随后按时间做前向 DP：跳过当前时刻支付该时刻损失，或启用护盾并跳到作用和冷却结束后，支付这段区间的损失减去保护量。两类转移覆盖下一次启用的全部可能，区间互不重叠，故可得到最小总损失。

Codex（GPT-6）采用后向 DP：将不启用护盾的总损失作为固定基线，只累计被保护的收益。这与前向损失 DP 等价，差分与单调队列也相同。实现时须区分逐时刻损失和累计损失，并正确计算闭区间长度。设位置数为 $W$ 、时间范围为 $T$ 、输入记录总数为 $I$ ，两者时间和存储上界均为 $O(I+WT)$ .

## 无护盾时的损失

令 $W$ 为工事坐标跨度加一，$T$ 为最后一个事件的结束时刻。没有事件时直接输出 $0$ .

在“位置、时刻”的二维网格上，用二维差分记录事件。轰炸贡献 $+H$ ，维修贡献 $-H$ .求二维前缀和后，得到位置 $x$ 、时刻 $t$ 的净损失 $d_{x,t}$ .

设 $c_{x,t}$ 为位置 $x$ 在时刻 $t$ 开始时已建成的工事数，用建成时刻的前缀计数得到。无护盾总损失为

$$B=\sum_x\sum_{t=1}^{T}c_{x,t}d_{x,t}$$

再对每个位置的净损失沿时间做前缀和，记为 $P_{x,t}$ .

## 一次开启的收益

若在时刻 $t$ 开启护盾，结束时刻截断为 $e=\min(T,t+R_s-1)$ .位置 $x$ 能避免的净损失为

$$g_{x,t}=c_{x,t}(P_{x,e}-P_{x,t-1})$$

这里固定使用开启时刻的工事数 $c_{x,t}$ ，因此不会错误保护后来建成的工事。维修贡献可能使 $g_{x,t}$ 为负。

选择端点距离不超过 $M$ 的闭区间，等价于选择最多 $M+1$ 个连续整数坐标。对 $g_{x,t}$ 做位置前缀和，用单调队列维护允许范围内最小的左端前缀，即可在 $O(W)$ 时间内求出本次最大收益 $G_t$ .收益允许取 $0$ ，表示不使用护盾。

## 时间上的动态规划

令 $F_t$ 表示设备在时刻 $t$ 可用时，从此刻开始最多能避免的净损失。令 $F_{T+1}=0$ ，从后向前计算：

$$F_t=\max\left(F_{t+1},\ G_t+F_{\min(T+1,t+R_s+S)}\right)$$

第一项跳过时刻 $t$ ；第二项在当前时刻开启一次，并在设备下次可用时继续安排。不同次护盾的生效时间不相交，因此收益可以相加。最终答案是 $B-F_1$ .

## 正确性与边界

二维差分准确还原每个时刻各事件的总效果；工事计数只包含已经建成的工事，因此 $B$ 是无护盾损失。公式 $g_{x,t}$ 恰好计算一次护盾挡住的轰炸与维修总和，单调队列穷尽所有合法区间。任意最优安排在设备可用时，要么等待，要么立即开启；转移枚举了这两种情况。因此 $F_1$ 是最大可避免损失，所得答案最小。

需要注意 $M=0$ 仍对应一个坐标、损失允许为负、建成时刻等于开启时刻可以被保护，以及事件可能覆盖工事尚未建成的时段。

时间复杂度 $O(n+A+B+WT)$ ，空间复杂度 $O(n+A+B+WT)$ ；$W,T\le3000$ .损失、收益和动态规划值使用 64 位整数。输入数组在转为网格后及时释放。