矩阵消除游戏（状压）

链接：https://ac.nowcoder.com/acm/problem/200190
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

牛妹在玩一个名为矩阵消除的游戏，矩阵的大小是

牛妹想最大化她的得分，球球你帮帮她吧！

输入描述:

第一行三个整数

输出描述:

输出一个整数表示牛妹能获得的最大分数。

示例1

输入

输出

备注:

1

首先考虑贪心，如果每次贪心地选矩阵中剩下的最大的一行或者一列，然后把这一行（列）抹为0可以吗？

其实这样是不可取的，每次贪心选最大的是会影响后面的选取，局部最优解无法得到全局最优解，所以我们还是要枚举情况

由1≤n,m≤15，暗示可以状压，直接状压走起

直接看代码吧，注释很详细了（要有位运算基础）

 1 #include <bits/stdc++.h>
 2 typedef long long LL;
 3 #define pb push_back
 4 #define mst(a) memset(a,0,sizeof(a))
 5 const int INF = 0x3f3f3f3f;
 6 const double eps = 1e-8;
 7 const int mod = 1e9+7;
 8 const int maxn = 1e6+10;
 9 using namespace std;
10 
11 int G[20][20];
12 int line[20];  //一行上的总值
13 int col[20];  //一列上的总值
14 
15 int main()
16 {
17     #ifdef DEBUG
18     freopen("sample.txt","r",stdin); //freopen("data.out", "w", stdout);
19     #endif
20     
21     int n,m,k;
22     scanf("%d %d %d",&n,&m,&k);
23     for(int i=1;i<=n;i++) //输入
24     {
25         for(int j=1;j<=m;j++)
26         {
27             scanf("%d",&G[i][j]);
28             line[i] += G[i][j];
29         }
30     }
31     k = min(k,min(n,m));  //当k大于min(n,m)时可以全取完
32     LL ans = 0;
33     for(int i=0;i<=(1<<n)-1;i++)
34     {
35         int numl = __builtin_popcount(i);  //通过i中有多少个1判断取了多少行
36         int numc = k-numl;  //计算要取多少列
37         if(numc>m||numc<0) continue;  //直接continue掉不可取的情况,numc>m(不够贪),numc<0(不可能)
38 
39         LL sum = 0;
40         mst(col);  //不清数组试试
41         for(int j=0;j<n;j++)  //遍历每一行
42         {
43             int flag = 0;  //判断该行取没取
44             if((1<<j)&i) flag = 1;
45             if(flag) sum += line[j+1];  //取该行
46             for(int h=1;h<=m;h++)  //遍历每一列
47                 if(!flag) col[h] += G[j+1][h];  //如果没取该行,就把该行的数加到对应的列col中
48         }
49         sort(col+1,col+1+m);  //按col值排序
50         for(int j=m;numc>0;j--,numc--)  //先取col值大的,取numc个
51             sum += col[j];
52         ans = max(ans,sum);  //更新ans
53     }
54     printf("%lld
",ans);
55     
56     return 0;
57 }