https://codeforces.com/contest/1209/problem/E2
题意：
给定一个N×M 的矩阵，你可以对每一列的数字进行任意次的旋转操作（即整体向上或者整体向下）。输出在做出任意次旋转操作后每一行的最大值之和。
解题思路：看到n的范围很小，可以联想到状压DP来解，设dp【i】为状态i的最大值，所谓状态i，就是在i的二进制下，某位置为1则表示该行已找到最大值，为0则没有找到最大值，那么可以进行子集DP了。还有值得注意的是，我们最少可以在min（n，m）列中找打答案，所以先按每列的最大值排序，取前min（n，m）列就好了。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e3+5;
int dp[1<<12];
int f[1<<12];
int f1[1<<12];
struct st{
int id,w;
bool operator < (const st & tem)const{
return w>tem.w;
}
}stm[maxn];
int a[15][maxn];
int use[maxn];
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,m;
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 i=0;i<m;i++){
int tem=0;
for(int j=0;j<n;j++){
tem=max(tem,a[j][i]);
}
stm[i].id=i;
stm[i].w=tem;
}
sort(stm,stm+m);
memset(use,0,sizeof(use));
memset(dp,0,sizeof(dp));
for(int i=0;i<n&&i<m;i++){
use[stm[i].id]=1;
}
for(int i=0;i<m;i++){
if(use[i]==0){
continue;
}
for(int k=0;k<n;k++){
for(int j=0;j<(1<<n);j++){
f1[j]=max(f1[j],f[j]);
f[j]=dp[j];
for(int kk=0;kk<n;kk++){
int tem=(k+kk)%n;
if((j&(1<<tem))){
f[j]=max(f[j],f[j^(1<<tem)]+a[kk][i]);
}
}
}
}
for(int j=0;j<(1<<n);j++){
dp[j]=max(f1[j],f[j]);
f1[j]=0;
f[j]=0;
}
}
printf("%d\n",dp[(1<<n)-1]);
}
return 0;
}
Codeforces Round #584 E2. Rotate Columns (hard version)（状压DP）
原文：https://www.cnblogs.com/Zhi-71/p/11605494.html