力场护盾：题解¶

解法比较¶

出题人解法用时间与位置的二维差分还原伤害，统计启用时可被保护的建筑，再用空间前缀和与单调队列求每个时刻的一次最大保护量。随后按时间做前向 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 位整数。输入数组在转为网格后及时释放。