题解 CF1209E2 【Rotate Columns (hard version)】
Published:
题意描述：$T$ 次询问，每次给定一个 $n*m$ 的矩阵，每次可以将一列循环任意次。设 $r_i$ 表示第 $i$ 行的最大值，求所有可能的操作下 $\sum r_i$ 最大值。 $(T\le40,n\le12,m\le2e3)$
考虑到 $n$ 很小，显然就是状态压缩，但是 $m$ 很大，而且乘 $2^n$ 完全不能过，所以就思考这 $m$ 个必是唬人的。先猜一个结论，我们只用取每列最大值排名前 $n$ 的。考虑为什么。当我们取第 $n+1$ 大的那一列的时候，我们选前 $n$ 名取满一定不会更劣，而第 $n+1$ 大的那一列中不存在比那个列的最大值排名第 $n+1$ 的值更大的值了，所以必然不劣。然后就是对 $n*n$ 的矩阵求原值，这个用状态压缩 $dp$ 可以轻易通过。 设 $dp[i][j]$ 表示选到第 $i$ 列，强制选了状态为 $j$ 的行的最大值。时间复杂度$O(n3^n)$。
#include<bits/stdc++.h>
#define re register
#define ll long long
#define LL inline ll
#define I inline int
#define V inline void
#define B inline bool
#define FOR(i,a,b) for(re int i=(a),i##i=(b);i<=i##i;++i)
#define ROF(i,a,b) for(re int i=(a),i##i=(b);i>=i##i;--i)
//#define gc getchar()
#define gc (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin),ft==fs))?0:*fs++
using namespace std;
char *fs,*ft,buf[1<<18];
const int N=1e4+10;
LL read(){
ll p=0; bool w=0; char ch=gc;
while(!isdigit(ch)) w=ch=='-'?1:0,ch=gc;
while(isdigit(ch)) p=p*10+ch-'0',ch=gc;
return w?-p:p;
}
int T,n,m,a[30][N],mx[N],ans;
int dp[2][N],f[20][N],sck[20],fl;
I get(int x,int zt){
int res=0,as=0,tmp=zt;
FOR(i,1,n){
tmp=zt,as=0;
FOR(j,i,i+n-1) (as+=(tmp&1)?a[j][x]:0),tmp>>=1;
res=max(res,as);
}
return res;
}
V sol(){
int tot=(1<<n)-1,tmp=0,bj=0;
FOR(k,1,n) {
tmp=0,bj=0;
FOR(i,1,m) if(mx[i]>tmp) tmp=mx[i],bj=i;
sck[k]=bj,mx[bj]=0;
}
FOR(k,1,n) FOR(j,0,tot) f[k][j]=get(sck[k],j);
FOR(i,1,n){
FOR(j,0,tot){
int w=tot^j;
dp[fl][j]=max(dp[fl][j],dp[fl^1][j]);
for(re int k=w;k;k=(k-1)&w)
dp[fl][j|k]=max(dp[fl][j|k],dp[fl^1][j]+f[i][k]);
}
fl^=1;
memset(dp[fl],0,sizeof(dp[fl]));
}
fl^=1;
ans=dp[fl][tot];
printf("%d\n",ans);
return ;
}
V init(){
memset(mx,0,sizeof(mx));
memset(dp,0,sizeof(dp));
return ;
}
int main(){
T=read();
while(T--){
n=read(),m=read(),ans=0;
init();
FOR(i,1,n) FOR(j,1,m) a[i][j]=read(),mx[j]=max(mx[j],a[i][j]);
FOR(i,n+1,2*n) FOR(j,1,m) a[i][j]=a[i-n][j];
sol();
}
return 0;
}