CF1209E Rotate Columns

题意

给出一个矩阵，可以选择一个列循环移位，求每一行的最大值的最大和

数据范围：$1 \le n \le 12,1 \le m \le 2000$

题解

我们可以记录每一列的选择情况，容易想到这是状压$dp$
用$dp[i][j]$表示前$i$列的选择情况为$j$的和，其中$j$的第$k$位表示选择第$k$行
但是由于$m$较大，这样会太慢
我们可以按每一列的最大值对列从大到小排序，容易证明，只会选择前$n$大的列，而剩下的列显然不会对答案造成影响

for(int j=0;j<m;j++){
    for(int i=0;i<n;i++)
        v[j]=Max(v[j],a[i][j]);
    c[j]=(node){v[j],j};
}
sort(c,c+m);
m=Min(n,m);

我们可以进行预处理，用$f[i][j]$表示第$i$列的选择情况为$j$的和，$j$的第$k$位表示选择第$i$列的第$k$行，即$a[k][i]$

tot=1<<n;
for(int i=0;i<m;i++)
    for(int j=0;j<tot;j++)
        for(int k=0;k<n;k++)
            if((j>>k)&1)
                f[i][j]+=a[k][c[i].id];

操作中$j$循环移位$k$次后的状态$t$可以表示为

int t=((j>>k)|(j<<(n-k)))&(tot-1);

$j$共有$n$种变化；因为可以任意进行操作，所以$$f[i][j]=max(f[i][t])$$
接下来进行$dp$
如果不在当前列选择，直接从之前继承

dp[i+1][j]=dp[i][j];

否则，对于一个状态$j$，从低位到高位枚举前$i$列选择的行，而第$i+1$列选择的自然就是剩下的行，我们将其状态记为$t$，那么前$i$列的状态就是$j \oplus t$

for(int t=j;t;t=(t-1)&j)
    dp[i+1][j]=Max(dp[i+1][j],dp[i][j^t]+f[i][t]);

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=12+1;
const int M=2000+10;
int t,n,m;
int a[N][M];
int tot;
int v[M],f[N][1<<N],dp[N][1<<N];
template <typename T>
inline T Max(T a,T b){
    return a>b?a:b;
}
template <typename T>
inline T Min(T a,T b){
    return a<b?a:b;
}
struct node{
    int v,id;
    inline bool operator < (const node& x) const{
        return v>x.v;
    }
} c[M];
int main(){
    scanf("%d",&t);
    for(;t--;){
        memset(v,0,sizeof(v));
        memset(f,0,sizeof(f));
        memset(dp,0,sizeof(dp));
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                scanf("%d",&a[i][j]);
        for(int j=0;j<m;j++){
            for(int i=0;i<n;i++)
                v[j]=Max(v[j],a[i][j]);
            c[j]=(node){v[j],j};
        }
        sort(c,c+m);
        m=Min(n,m);
        tot=1<<n;
        for(int i=0;i<m;i++){
            for(int j=0;j<tot;j++)
                for(int k=0;k<n;k++)
                    if((j>>k)&1)
                        f[i][j]+=a[k][c[i].id];
            for(int j=0;j<tot;j++)
                for(int k=0;k<n;k++){
                    int t=((j>>k)|(j<<(n-k)))&(tot-1);
                    f[i][j]=Max(f[i][j],f[i][t]);
                }
        }
        for(int i=0;i<m;i++)
            for(int j=0;j<tot;j++){
                dp[i+1][j]=dp[i][j];
                for(int t=j;t;t=(t-1)&j)
                    dp[i+1][j]=Max(dp[i+1][j],dp[i][j^t]+f[i][t]);
            }
        printf("%d\n",dp[m][tot-1]);
    }
    return 0;
}