题解：AT_utpc2021_e Bounding Box

one_last_kiss · 2025-10-24 19:22:16 · 题解

思路

很显然可以想到我们只用 j( 1 \le j \le 4) 个点来贡献边界值，剩余 k-j 个点一定优先先选择权值大的点。

所以我们先按照 c_i 从小到大排序，用 dp_{j,s} 求选 j 个点贡献状态为 s 的边界贡献值，剩下就用权值大的点补全就好了，即维护后缀和和边界情况。

预处理 f_s 为当前点在状态 s 的边界贡献和权值贡献值，那么转移方程即为：

最后枚举未覆盖的状态，后缀信息补全就好了。