预处理+状态压缩+剪枝——codefoece 1209E

那一步剪枝实在是没想到

#include<bits/stdc++.h>

using namespace std;

#define N 2005

struct Col{

    int MAX,a[],Max[<<];

}col[N];

int n,m,dp[][<<];

int cmp(Col &a,Col &b){return a.MAX>b.MAX;}

inline int judge(int s,int ss){

    for(int i=;i<;i++)

        if(!(s>>i & ) && (ss>>i & ))return ;

    return ;

}

vector<int>v[<<];

void init(){

    memset(dp,,sizeof dp);

    memset(col,,sizeof col);

}

int main(){

    int t;cin>>t;

    for(int i=;i<(<<);i++){

        for(int j=;j<=i;j++)

            if(judge(i,j))

                v[i].push_back(j);

    }

    //for(auto ss:v[3])cout<<ss<<" ";

    while(t--){

        init();

        cin>>n>>m;

        for(int i=;i<n;i++)

            for(int j=;j<m;j++){

                scanf("%d",&col[j].a[i]);

                col[j].MAX=max(col[j].MAX,col[j].a[i]);

            }

        sort(col,col+m,cmp);

        m=min(m,n);//只要用到最大值最大的前n列即可

        for(int j=;j<m;++j){

            Col cur=col[j];

            for(int p=;p<n;++p)

                for(int s=;s<(<<n);++s){

                    int sum=;

                    for(int k=;k<n;++k)

                        if(s>>k & )sum+=cur.a[(p+k)%n];

                    col[j].Max[s]=max(col[j].Max[s],sum);

                }

        }

        for(int s=;s<(<<n);s++)

            dp[][s]=col[].Max[s];

        for(int j=;j<=m;j++){

            for(int s=;s<(<<n);s++){

                //for(int ss=0;ss<=s;ss++)if(judge(s,ss))//ss是s的子集

                for(auto ss:v[s]){

                    //cout<<ss<<" ";

                    dp[j][s]=max(dp[j][s],dp[j-][s-ss]+col[j].Max[ss]);

                }

                //puts("");

            }

        }

        cout<<dp[m][(<<n)-]<<'\n';

    }

}