题解

思路

用四种符号展开消去两个绝对值，然后从左到右扫描，记录已选元素数和当前区间的开放状态。

做法

绝对值的四种符号

对一个区间 $[l,r]$，有

$$|b_l-a_r|+|b_r-a_l| =\max_{p,q\in\{-1,1\}}(p b_l-q a_l)+(q b_r-p a_r).$$

因而，区间开始时只需记住 $(p,q)$ 四种状态之一，区间结束时加上对应的右端贡献。

子任务 1：区间集枚举

当 $n\le12$ 时，按位置搜索：或不覆盖当前位置，或枚举以当前位置为左端点的下一个区间。搜索后续位置时只需记录还需覆盖的长度。该算法按定义直接验证答案，复杂度为指数级。

子任务 2：枚举最后一段

令 $f[i][j]$ 表示只使用前 $i$ 个位置，覆盖总长度为 $j$ 的最大答案。最后一个区间若为 $[l,i]$，则从 $f[l-1][j-(i-l+1)]$ 转移。枚举 $i,j,l$ 可在 $O(n^2k)$ 时间内求解，适用于 $n\le80$。

满分算法：扫描线动态规划

从左到右扫描位置。设 $dp[j]$ 为扫描过的位置中已覆盖 $j$ 个元素，且当前没有未结束区间的最优值。设 $open_{p,q}[j]$ 为已覆盖 $j$ 个元素，并有一个符号为 $(p,q)$ 的区间仍然开放的最优值。

对当前位置 $i$：

• 从 $dp[j]$ 可以跳过 $i$；
• 从 $dp[j-1]$ 加上 $p b_i-q a_i$ 可以开启新区间；
• 从 $open_{p,q}[j-1]$ 可以将开放区间延伸到 $i$；
• 在开启或延伸后，加上 $q b_i-p a_i$ 即可在 $i$ 结束区间。

一个长度为 $1$ 的区间同时执行开启和结束转移。最终答案是扫描全部位置后的 $dp[k]$。

复杂度

时间复杂度为 $O(nk)$，空间复杂度为 $O(k)$。