CF1209E2 Rotate Columns (hard version)

题意：

题目

分析：

首先我们看看数据范围： \(n<=12\) 这很显然是一个十分小的一个范围，提示我们可以使用各种怪解时间复杂度较大的解法去做。

先不考虑 \(m\) 的数据范围，我们可以很显然的想出一个状压 dp:

设 \(f[i][s]\) 考虑到第 \(i\) 列时，是行状态为 \(s\)(就是考虑哪些行计入答案)时，答案的最大值。

那么我们可以枚举当前列所选行的状态 \(s_0\) ，那么肯定满足 \(s_0\) 为 \(s\) 的子集。

设 \(val[i][s]\) 为第 \(i\) 列 行状态为 \(s\) 时的贡献最大值。

则显然有：\(f[i][s]=\max(f[i][s],f[i-1][s \oplus s_0]+val[i][s_0])\)

val 很容易在 \(O(2^n m n^2)\) 中解决。

但是递推的过程时间复杂度高达 \(O(3^nm)\)，会炸。

所以我们考虑优化。

这里有一个贪心：

当 \(n<m\) 时，只有列中元素最大值前 \(n\) 个的列可能对答案有贡献。因为假如有其他的列对答案有贡献，那么一定可以被未被选中的前 \(n\) 列中的一个最大值所替换，答案显然可以更优。

所以此时 \(m\) 的数据规模就和 \(n\) 一样了。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N=13,M=2000+10;
int a[N][M],n,m;
int maxcol[M],rk[M];
int f[N][(1<<N)+10],val[N][(1<<N)+10],tmp[N*2];

void init(){
	memset(maxcol,0,sizeof maxcol);
	memset(f,0,sizeof f);
	memset(val,0,sizeof val);
	for(int i=1;i<=m;i++)rk[i]=i;
	return;
}

bool cmp(int x,int y){
	return maxcol[x]>maxcol[y];
}

signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>a[i][j];
			}
		}
		init();
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				maxcol[j]=max(maxcol[j],a[i][j]);
			}
		}
		sort(rk+1,rk+m+1,cmp);
		m=min(n,m);
		for(int id=1;id<=m;id++){
			int i=rk[id];
			//cout<<i<<" ";
            for(int j=1;j<=n;j++){
            	tmp[j]=tmp[j+n]=a[j][i];
			}
			for(int s=0;s<(1<<n);s++){
				for(int j=1;j<=n;j++){
					int cnt=0;
					for(int k=1;k<=n;k++){
						if((1<<k-1)&s){
							cnt+=tmp[k+j-1];
							//cout<<id<<" "<<s<<" "<<tmp[k+j-1]<<endl;
						}
					}
					val[id][s]=max(val[id][s],cnt);
				}
				//cout<<id<<" "<<s<<" "<<val[id][s]<<endl;
			}
		}
		for(int i=1;i<=m;i++){
			for(int s=0;s<(1<<n);s++){
				//cout<<f[i][s]<<endl;
				f[i][s]=f[i-1][s];
				for(int s0=s;s0;s0=(s0-1)&s){
					f[i][s]=max(f[i][s],f[i-1][s^s0]+val[i][s0]);
				}
			}
		}
		cout<<f[m][(1<<n)-1]<<"\n";
	}

	return 0;
}
/*
1
3 3
9 9 9
1 1 1
1 1 1
*/