CF1209E2 Rotate Columns (hard version) 题解

CF1209E2

给定 \(n \times m\) 的矩阵，可以对每一列进行若干次循环移位，求操作完成后每一
行的最大值之和的最大值。

\(1 \leq n \leq 12, 1 \leq m \leq 2000\)

• 这里 \(m\) 很大，但有一个很重要的性质

• 这 \(m\) 列中只有最大的前 \(n\) 个会对答案产生贡献

• 因此我们直接就把 \(m\) 削到了 \(\leq 12\) 的范围

• 这么小，当然可以状压啦

• 设 \(dp_{i,S}\) 表示考虑了前 \(i\) 列数，集合 \(S\) 中的行的最大值已经确定，集合 \(S\) 中的最大值之和

• 可以得到转移：

• \[dp_{i,S} \leftarrow dp_{i-1,T} + \sum_{j \in S, j \notin T} a_{(j + \Delta)\mod n,i} \]

• 总复杂度为 \(O(n3^n)\)

• 这题的关键就在于，也许这么算的最大值会比真实答案要小，但正是因为原题要求最大值，我们可以直接忽略他的错误选择方式，因为最终获得的答案一定是合法解