题解

思路

令 $dp_i$ 是只考虑前 $i$ 个格子的全部美丽值中最大的至多 $k$ 个，按非递增排列。若第 $i$ 格不涂色，候选表是 $dp_{i-1}$；若包含 $i$ 的最后一个极大涂色段为 $[l,i]$，则 $l-1$ 必须不涂色，候选表是 $dp_{l-2}$ 的每个元素加 $a_{l,i}$（$l=1$ 时前缀只有空方案 $0$）。

做法

每个候选表已经有序。把各表首元素放进大根堆，每次取最大值写入 $dp_i$，再把同一表的下一元素放入堆，直到取够 $\min(k,2^i)$ 个。这是经典的多个有序表前 $k$ 大归并。

小规模程序枚举所有涂色掩码；$k=1$ 分支只保留每个前缀的最大值。独立 Oracle 使用可恢复的优先队列保存各 $dp$ 表，构建下一层时临时弹出再恢复，和标程的只读向量下标实现相互核验。

正确性证明

任意前 $i$ 格方案恰有两类：第 $i$ 格不涂色；或存在唯一的最后极大涂色段 $[l,i]$。后一类在 $l\ge2$ 时第 $l-1$ 格不涂色，其左侧恰是任意前 $l-2$ 格方案。因此转移列出的有序表不重不漏地表示全部 $2^i$ 个方案。多路归并每次取当前所有表头的最大者，而每个表未取部分都不大于其表头，故依次得到全体候选的前 $k$ 大。归纳可得最终 $dp_n$ 正确。

复杂度

读入矩阵需要 $O(n^2)$ 时间；动态规划需要 $O(nk\log n)$ 时间和 $O(nk+n^2)$ 空间。