526互联

CF1866D Digital Wallet 题解

发布时间 2023-11-04 08:26:38作者: FOX_konata

Problem - 1866D - Codeforces

Digital Wallet - 洛谷

  • 不妨为选数钦定一个顺序：不同行之间无影响，列从左到右取一定不劣。

    • 设计状态：设 \(dp_{i,j}\) 表示前 \(i\) 次操作操作到第 \(j\) 列的最大答案

    • 转移：因为对于同一列不互相影响， 因此枚举这一列取 \(c\) 个数，显然取这一列数的前 \(c\) 大。

    • \(dp_{i,j} \leftarrow \min dp_{i-1,k}+sum_{j,c}\)

    • 优化：发现 \(k \leq 10\) ，因此给 dp 状态的第二项加上一个偏移量

  • 最终复杂度 \(O(nmk)\)