状压DP--Rotate Columns (hard version)-- Codeforces Round #584 - Dasha Code Championship - Elimination Round (rated, open for everyone, Div. 1 + Div. 2)

  1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);
  2 #include <cstdio>//sprintf islower isupper
  3 #include <cstdlib>//malloc  exit strcat itoa system("cls")
  4 #include <iostream>//pair
  5 #include <fstream>//freopen("C:\\Users\\13606\\Desktop\\草稿.txt","r",stdin);
  6 #include <bitset>
  7 //#include <map>
  8 //#include<unordered_map>
  9 #include <vector>
 10 #include <stack>
 11 #include <set>
 12 #include <string.h>//strstr substr
 13 #include <string>
 14 #include <time.h>//srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
 15 #include <cmath>
 16 #include <deque>
 17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less
 18 #include <vector>//emplace_back
 19 //#include <math.h>
 20 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor
 21 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)
 22 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
 23 //******************
 24 int abss(int a);
 25 int lowbit(int n);
 26 int Del_bit_1(int n);
 27 int maxx(int a,int b);
 28 int minn(int a,int b);
 29 double fabss(double a);
 30 void swapp(int &a,int &b);
 31 clock_t __STRAT,__END;
 32 double __TOTALTIME;
 33 void _MS(){__STRAT=clock();}
 34 void _ME(){__END=clock();__TOTALTIME=(double)(__END-__STRAT)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;}
 35 //***********************
 36 #define rint register int
 37 #define fo(a,b,c) for(rint a=b;a<=c;++a)
 38 #define fr(a,b,c) for(rint a=b;a>=c;--a)
 39 #define mem(a,b) memset(a,b,sizeof(a))
 40 #define pr printf
 41 #define sc scanf
 42 #define ls rt<<1
 43 #define rs rt<<1|1
 44 typedef long long ll;
 45 const double E=2.718281828;
 46 const double PI=acos(-1.0);
 47 //const ll INF=(1LL<<60);
 48 const int inf=(1<<30);
 49 const double ESP=1e-9;
 50 const int mod=(int)1e9+7;
 51 const int N=(int)1e6+10;
 52 
 53 int a[15][2005];
 54 struct node
 55 {
 56     int id,max_;
 57     friend bool operator<(node a,node b)
 58     {
 59         return a.max_>b.max_;
 60     }
 61 }key[2005];
 62 int dp[5000],DP[5000];
 63 
 64 void solve()
 65 {
 66     int n,m;
 67     sc("%d%d",&n,&m);
 68     for(int i=1;i<=m;++i)
 69         key[i]={i,0};
 70     for(int i=1;i<=n;++i)
 71         for(int j=1;j<=m;++j)
 72             sc("%d",&a[i][j]),key[j].max_=max(key[j].max_,a[i][j]);
 73     sort(key+1,key+1+m);
 74     m=minn(m,n);
 75     int top=(1<<n)-1;
 76     for(int i=0;i<=top;++i)DP[i]=0;
 77     for(int o=1;o<=m;++o)
 78     {
 79         for(int i=0;i<=top;++i)dp[i]=0;
 80         for(int i=0;i<=top;++i)
 81         {
 82             int sum=0;
 83             for(int pos=0;pos<n;++pos)
 84                 if((i>>pos)&1)
 85                     sum+=a[pos+1][key[o].id];
 86             for(int j=1,now=i;j<=n;++j)
 87             {
 88                 dp[now]=max(dp[now],sum);
 89                 if(now&1)now+=1<<n;
 90                 now>>=1;
 91             }
 92         }
 93         for(int i=top;i>=0;--i)//注意要从大到小开始更新,因为大的要用到小的;
 94         {
 95             for(int k=i;k;k=(k-1)&i)
 96                 DP[i]=max(DP[i],DP[i-k]+dp[k]);
 97         }
 98     }
 99     pr("%d\n",DP[top]);
100 }
101 
102 int main()
103 {
104 //    cout<<(1<<12)<<endl;
105     int T;
106     sc("%d",&T);
107     while(T--)solve();
108     return 0;
109 }
110 
111 /**************************************************************************************/
112 
113 int maxx(int a,int b)
114 {
115     return a>b?a:b;
116 }
117 
118 void swapp(int &a,int &b)
119 {
120     a^=b^=a^=b;
121 }
122 
123 int lowbit(int n)
124 {
125     return n&(-n);
126 }
127 
128 int Del_bit_1(int n)
129 {
130     return n&(n-1);
131 }
132 
133 int abss(int a)
134 {
135     return a>0?a:-a;
136 }
137 
138 double fabss(double a)
139 {
140     return a>0?a:-a;
141 }
142 
143 int minn(int a,int b)
144 {
145     return a<b?a:b;
146 }