题解：CF1209E1 Rotate Columns (easy version)

· · 题解

首先每一行的最大值之和的最大值，等价于在每一行都任意选一个数，这些数的和的最大值。

考虑状压 DP。设 f(i, S) 表示若考虑前 i 列，已经确定的行组成的集合为 S，选出的数的最大和。

转移首先让第 i 列循环移位。然后枚举第 i 列选了哪些行。令这些行的集合为 T。那么：

f(i, S) = \max_{T \subseteq S}\left(\sum_{u \in T}a_u + f(i - 1, S/T)\right)

答案为 f(m, \{1,2,\dots,n\})。把上面说的集合改成状态压缩实现即可。

https://codeforces.com/contest/1209/submission/275189194

E2 题解交不了了，在 E1 题解里一块写了。

> 反证法。如果某一列的最大值不是前 $n$ 大，且我们在某些行我们选的数是这一列的。我们知道「这一列的数」$\le $「这一列的最大值」，而「这一列的最大值」$\le$「前 $n$ 大的列中，把最大放在这些行上的列的最大值」。所以不优。 所以我们将列数降到了 $n$。这是第一个优化。 第二个优化是，预处理 $w(i, j, S)$ 表示将第 $i$ 列循环移位 $j$ 次后，$\sum_{u \in S} a_{u,i}$ 的值。再维护 ${w_{\max}}_{i, S} = \max_{j=0}^{n-1} w(i, j, S)$。转移时直接查表即可。 <https://codeforces.com/contest/1209/submission/275196043>