一、题目
点此看题
二、解法
首先可以缩小数据范围，你会发现如果将每一列按最大值排序，那么 较大时取前 列算答案即可。
要将题目求的东西做一个转化，每一行的最大值转化成每一行至多选一个数（反正要求总和最大），这样就一定会选每一行的最大值。设 为处理到了第 列，行是否选了数的状压为 。
转移要预处理算出旋转情况下的子集总和最大值，这一列的一个状态
旋转
次得到的状态是((j>>d)|(j<<n-d))&((1<<n)-1)，那么在
取
时找最大值即可。转移过程枚举子集的子集，所以时间复杂度
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 2005;
int read()
{int x=0,f=1;char c;while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
int T,n,m,dp[20][1<<12],sum[1<<12];
struct node
{int a[20],mx;bool operator < (const node &b) const{return mx>b.mx;}
}s[M];//下标是列
signed main()
{T=read();while(T--){n=read();m=read();for(int j=1;j<=m;j++)s[j].mx=0;for(int i=0;i<n;i++)for(int j=1;j<=m;j++){s[j].a[i]=read();s[j].mx=max(s[j].mx,s[j].a[i]);}sort(s+1,s+m+1);memset(dp,0,sizeof dp);for(int i=1;i<=min(n,m);i++){memset(sum,0,sizeof sum);for(int j=1;j<(1<<n);j++)for(int k=0;k<n;k++)if(j&(1<<k))sum[j]=sum[j^(1<<k)]+s[i].a[k];for(int j=1;j<(1<<n);j++)for(int d=0;d<n;d++){int k=((j>>d)|(j<<n-d))&((1<<n)-1);sum[j]=max(sum[j],sum[k]);}for(int j=1;j<(1<<n);j++)for(int k=j;;k=(k-1)&j){dp[i][j]=max(dp[i][j],dp[i-1][k^j]+sum[k]);if(k==0) break;}}printf("%d\n",dp[min(n,m)][(1<<n)-1]);}
}