Codeforces 1209E2 Rotate Columns
题目链接
https://codeforces.com/problemset/problem/1209/E2
题目大意
给你一个 $n \times m$ 的矩阵，你可以将每一列中的数循环排列，问每一行的最大值的和最大为多少。
题目分析
看到 $n \leq 12$ 的条件立马想到状压 $DP$。令 $F[S]$ 表示集合 $S$ 中的行最大值都已经被确定。那么显然可以对于每一列都求出每种集合在这一列的 $n$ 种排列方法下的最大值。那么可以通过按列添加枚举子集来进行 $DP$。这时复杂度是 $O(Tm(n2^n+3^n))$。显然有点大，只能通过 $n\leq 4$ 的 $E1$。如果把 $m$ 列都跑了显然有很多列其实是一个元素都用不上的。如果那把这些列想办法删掉就可以减小复杂度。考虑我最多只需要前 $n$ 大的数。如果将所有的列按照该列的最大值排序，那么其实只需要跑最大的 $n$ 列就可以了。这样一来复杂度就变为 $O(Tn(n2^n+3^n))$ ，就可以通过这道题了。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000 + 5;
int t;
int n, m;
int a[20][maxn];
int b[50];
int c[maxn];
int maxx[maxn];
int f[15][(1<<13)];
int g[(1<<15)];
bool cmp(int x, int y){
return maxx[x] > maxx[y];
}
int solve(int x){
int i, j, k;
memset(g, 0, sizeof(g));
for(i=1;i<=n;i++){
b[i] = a[i][x];
}
for(i=n+1;i<=2*n;i++){
b[i] = a[i - n][x];
}
for(i=0;i<(1<<n);i++){
for(j=0;j<n;j++){
int ans = 0;
for(k=1;k<=n;k++){
if((i >> (k - 1)) & 1){
ans += b[j + k];
}
}
g[i] = max(g[i], ans);
}
}
return 0;
}
int main(){
int i, j, k;
scanf("%d", &t);
while(t--){
scanf("%d%d", &n, &m);
memset(maxx, 0, sizeof(maxx));
memset(f, 0, sizeof(f));
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
scanf("%d", &a[i][j]);
maxx[j] = max(maxx[j], a[i][j]);
c[j] = j;
}
}
sort(c + 1, c + m + 1, cmp);
for(i=1;i<=min(n,m);i++){
solve(c[i]);
for(j=0;j<(1<<n);j++){
f[i][j] = max(f[i][j], f[i - 1][j]);
for(k=j;k>0;k=((k-1)&j)){
f[i][j] = max(f[i][j], f[i - 1][j ^ k] + g[k]);
}
}
}
printf("%d\n", f[min(n, m)][(1<<n)-1]);
}
return 0;
}