题解

思路

先按座位 $S_i$ 递增排列工人。若两个被选区间分别属于座位更靠左和更靠右的工人，则前一个区间一定完全位于后一个区间左侧。于是可以用已经处理的木板前缀描述状态。

做法

两个结构子任务

若所有 $L_i=1$，工人只能粉刷互不相同的 $S_i$，答案为 $\sum P_i$。若 $k=1$，正利润保证最优区间长度为 $L_1$，答案为 $L_1P_1$。

二次动态规划

令 $dp_i[j]$ 表示只考虑前 $i$ 名工人，并且只使用前 $j$ 块木板时的最大收入。第 $i$ 名工人粉刷 $x+1$ 到 $j$ 时，需要

$$\max(0,j-L_i)\le x<S_i\le j\le\min(N,S_i+L_i-1).$$

转移为

$$dp_i[j]=\max\left(dp_{i-1}[j],dp_i[j-1],\max_x\{dp_{i-1}[x]+(j-x)P_i\}\right).$$

直接枚举 $x$ 的复杂度为 $O(kN^2)$。

单调队列优化

把最后一项改写为

$$jP_i+\max_x\{dp_{i-1}[x]-xP_i\}.$$

随着 $j$ 递增，合法 $x$ 构成滑动窗口 $[\max(0,j-L_i),S_i-1]$。用单调队列维护其中 $dp_{i-1}[x]-xP_i$ 的最大值，即可在均摊 $O(1)$ 时间完成一次转移。

每名工人结束后，$dp_i[j]=\max(dp_i[j],dp_i[j-1])$ 保证可以跳过未粉刷的木板；dp_{i-1} 与 dp_i 必须分离，避免同一名工人被重复使用。

正确性

按 $S_i$ 排序后，当前工人的非空区间包含 $S_i$。任何更早工人的非空区间若与它不相交，只能结束在当前区间起点之前，因此某个唯一的 $x$ 将两部分分开。转移枚举了所有合法 $x,j$，也允许当前工人不工作和末尾木板不粉刷，所以不会遗漏。反之，每次转移拼接的两部分不重叠，且新区间包含 $S_i$、长度不超过 $L_i$，因此一定合法。归纳可得最终状态等于最优收入。

复杂度

满分算法时间复杂度为 $O(kN)$，空间复杂度为 $O(N)$。