题解

思路

令一个点 $(x,y)$ 对应区间 $[x,k-y]$。三角形参数 $(a,b)$ 对应斜边区间 $[a,k-b]$，其代价为区间长度乘 $A$；该三角形能覆盖点，当且仅当点的区间完全包含在三角形区间中。

若两个最优方案中的三角形区间相交，可以把它们合并，合并后的长度不大于原长度之和，且覆盖点只会增加。因此存在一个最优方案，其中三角形区间两两不交。

先假设所有点均单独删除，总费用为 $C=\sum c_i$。使用区间 $[L,R]$ 的三角形能获得的净节省为

问题变成选择若干不交区间，使总节省最大，最后答案为 $C$ 减去最大节省。

做法

子任务 1：枚举单位段集合

把 $[0,k]$ 分成 $k$ 个单位段。任意被选择的单位段集合可按连续块合并为若干三角形区间，总代价为选择单位段数乘 $A$。点 $(x,y)$ 被三角形覆盖，当且仅当从 $x$ 到 $k-y-1$ 的所有单位段都被选择。

枚举 $2^k$ 个集合，直接计算三角形费用和未覆盖点的单删费用，取最小值。

子任务 2：二次动态规划

令 $dp_R$ 表示只考虑斜边坐标前缀 $[0,R]$ 时的最大节省。若最后一个三角形为 $[L,R]$，则由 $dp_L$ 转移。

扫描右端点 $R=1,2,\ldots,k$，对每个可能的左端点维护

右端点增加一时，所有 $L<R$ 的 $g_L$ 减去 $A$；每个满足 $k-y_i=R$ 的点会给所有 $L\le x_i$ 的 $g_L$ 加上 $c_i$。然后

直接循环维护所有左端点即可得到 $O(k^2+nk)$ 算法。

子任务 3：区间加与全局最大值

上述转移只需要：

• 对前缀 $[0,R-1]$ 加 $-A$；
• 对前缀 $[0,x_i]$ 加 $c_i$；
• 查询全局最大值；
• 在位置 $R$ 写入 $dp_R$。

用带懒标记的线段树维护这些操作。初始时位置 $0$ 为零，其余位置为负无穷。扫描完所有 $R$ 后，答案为 $C-dp_k$。

复杂度

三个层级的时间复杂度分别为 $O(2^k(n+k))$、$O(k^2+nk)$ 和 $O((n+k)\log k)$；满分算法空间复杂度为 $O(n+k)$。