CF#584 Div.1+2 E2. Rotate Columns (hard version) //状压dp+子集的子集

题目

题意：

给一矩阵，对于每一列，可以循环的滚动任意次，定义$r_i$为第$i$行的最大值，求$\sum r_i$的最大值。

思路：

定义$dp[i][j]$，遍历到第$i$列，二进制状态为$j$的最大值。
像E1这样暴力肯定不行，这里有两个优化。
发现每次转移当前二进制不能和前一列的二进制有重合的1，
那么如果当前二进制状态是$j$，可以遍历$j$的子集，然后通过子集转移。
也就是要遍历$(1<<n)-1$的子集的子集，复杂度为$O(3^n)$(详见：这里
另一个优化：最多只需要n列就可以求出最大值。

所以复杂度为$O(3^n\ast n\ast T)$

/*   Author : Rshs
 *   Data : 2019-09-16-13.27
 */
#include<bits/stdc++.h>
using namespace std;
#define FI first
#define SE second
#define LL long long
#define MP make_pair
#define PII pair<int,int>
#define SZ(a) (int)a.size()
const double pai = acos(-1);
const double eps = 1e-10;
const LL mod = 1e9+7;
const int MX = 1e6+5;
int dp[15][(1<<12)+5];
int now[15][(1<<12)+5];//每一列所有状态的最大值
int n,m,RRR; //min(n,m)
struct no{
    vector<int>v;
    int val;
}a[2005];
bool operator<(const no&x,const no &y){
    return x.val>y.val;
}

void Main(int avg){
    memset(dp,0,sizeof(dp));
    memset(now,0,sizeof(now));
    for(int i=0;i<2005;i++) a[i].v.clear();
    cin>>n>>m;RRR=min(n,m);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        int sa;scanf("%d",&sa);
        a[j].v.push_back(sa);
    }
    /******************************************************/
    for(int i=1;i<=m;i++){ //列最大值
        int mx=INT_MIN;
        for(auto j:a[i].v){
            mx=max(mx,j);
        }
        a[i].val=mx;
    }
    sort(a+1,a+1+m);
    for(int w=1;w<=RRR;w++){ //处理now
        deque<int>v;
        for(auto i:a[w].v)v.push_back(i);
        for(int i=1;i<=n;i++){
            for(int j=0;j<(1<<n);j++){
                int cc=0;
                for(int w=0;w<n;w++){
                    if(j&(1<<w)){
                        cc+=v[w];
                    }
                }
                now[w][j]=max(now[w][j],cc);
            }
            int tt=v.front();
            v.pop_front();
            v.push_back(tt);
        }
    }
    /******************************************************/
    for(int i=1;i<=RRR;i++){
        for(int j=0;j<(1<<n);j++) dp[i][j]=dp[i-1][j];
        for(int j=0;j<(1<<n);j++){
            for(int S=j;S!=0;S=(S-1)&j){
                dp[i][j]=max(dp[i][j],dp[i-1][j-S]+now[i][S]);
            }
        }
    }
    cout<<dp[RRR][(1<<n)-1]<<'\n';
}
int main(){
    int cas;cin>>cas;for(int i=1;i<=cas;i++)Main(i);
    return 0;
}