CF1209E Rotate Columns

发表于 分类于 ， ， 阅读次数：

题意：给出一个 行 列的矩阵，可以对列进行循环移位，最后的贡献是每一行的最大值的和。

最大化贡献。

多组数据，，，，时限 。

考虑 DP，对行状压。

表示考虑前 列，行集合 的最大值已经锁定，锁定的最大贡献和。

表示第 行经过循环移位能使得 的行对应位置的和的最大值。

容易 大力计算一组 。

转移时枚举子集 这样的复杂度是 的，无法通过。

有一个显而易见的贪心策略：只考虑每一列的最大值，取排名前 个的和。

这样虽然得不到最优解，但是得到了答案的一个下界 ：每一列的最大值前 个的和。

这样，我们只需保留最大值前在 个的行即可，这样可以使得 。

复杂度改进为 ，可以通过。