题解

思路

设入口 (i) 的人工防守区间为 (I_i)，连接的发电机工作区间为 (J)。从该入口进入的僵尸数为

[ x-|I_i\cup J|=x-m-|I_i|+|I_i\cap J|. ]

前半部分固定，因此要最大化所有交集长度之和。

所有发电机区间长度相同。把入口按 (l_i+r_i)，也就是人工区间中点的两倍排序后，固定若干发电机位置时，每个入口一定选择中点最近的发电机。因此每台发电机负责排序后的一段连续入口。

做法

记 (w(l,r)) 为只用一台发电机负责第 (l) 到第 (r) 个入口时，这一段能够得到的最大贡献，贡献已经包含

[ \sum_{i=l}^{r}(x-m-(r_i-l_i)). ]

一台发电机的启动时刻连续移动时，交集和是分段一次函数。若启动时刻没有碰到任何 (l_i)，结束时刻也没有碰到任何 (r_i)，向左或向右移动至少有一个方向不劣。因此最优启动时刻可取自

[ {l_i}\cup{r_i-m}, ]

并在边界 (0) 与 (x-m) 处截断。

子任务 1

枚举 (k) 台发电机的全部非降启动时刻。对每个入口选择交集最大的发电机，直接计算答案。

子任务 2

枚举左端点 (l)，逐步加入右端点 (r)。维护每个候选启动时刻与当前区间段的交集和，扫描全部候选即可得到 (w(l,r))。共有 (O(n^2)) 个区间段和 (O(n)) 个候选，预处理为 (O(n^3))。

随后做分段动态规划：

[ dp_{g,r}=\max_{l\le r}{dp_{g-1,l-1}+w(l,r)}. ]

满分算法

交集长度关于启动时刻是三段式一次函数。按 (l) 从 (r) 向左扩展时，用树状数组维护所有候选时刻上的斜率与常数，即可快速加入一个入口。

矩阵 (w) 满足四边形不等式，其最优候选时刻满足决策单调性：

[ opt(l,r-1)\le opt(l,r)\le opt(l+1,r). ]

只在两个已知决策之间扫描，就能求出全部 (w(l,r))。外层分段 DP 同样具有单调决策，可用分治优化计算每一层。由于 (k\le n)，整体能通过 (n=2000)。

正确性说明

容斥恒等式把目标精确转化为最大化交集和。等长发电机区间的最优匹配按中点保持顺序，所以每台发电机负责一个连续段，不会漏掉最优解。分段一次函数的斜率只有在 (l_i) 或 (r_i-m) 处变化，因此候选启动时刻集合完备。(w(l,r)) 精确表示一台发电机负责该段的最优贡献，分段 DP 枚举最后一段的左端点，故无重无漏。满分算法只用四边形不等式缩小扫描区间，没有删除最优决策，答案保持不变。

复杂度

子任务 1 枚举启动时刻；子任务 2 时间复杂度 (O(n^3+kn^2))，空间复杂度 (O(n^2))；满分算法时间复杂度 (O(n^2\log n))，空间复杂度 (O(n^2))。