審題：
本題需要我們找到消除矩陣行與列后可以獲得的最大權值

思路：
方法一：貪心+二進制枚舉

這里的矩陣消除時，行與列的消除會互相影響，所以如果我們先統計所有行和列的總和，然后選擇消除最大的那一行/列，選擇完后更新所有行和列的總和，再循環進行消除選擇，此時會導致部分情況無法得到最優解。

eg：進行回合數限制為2，矩陣如下圖

此時我們會先選擇第一列，然后更新各行列的總和

此時我們就再選擇第三行，選擇結束

不過其實我們完全一開始可以直接就選擇第一行和第三行，這樣子兩個回合就拿到了所有權值，所以這個策略是有問題的

正確貪心策略：先用二進制枚舉行的選擇情況，得到所有行的選取方案，然后失去了行的變動干擾，我們再對列求總和并取總和較大的前k-cnt列加入sum中即可，然后多組數據利用max維護一個最終答案answer

解題：
?

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 30;
int n,m,k;
int a[N][N];
int col[N];//計算每列總和
int answer;
int calcnt(int num)//計算有多少個1
{int count = 0;while(num){count++;num &= num-1;}return count;
}
bool cmp(int a, int b)
{return a > b;
}
int main()
{//數據錄入cin >> n >> m >> k;for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)cin >> a[i][j];//二進制枚舉所有行選擇情況for(int i = 0; i < (1 << n); i++){ int cnt = calcnt(i);//非法回合數直接跳過if(cnt  > k) continue;//多組數據除去殘留痕跡int sum = 0;memset(col,0,sizeof col);//完成對行和的累加和列和的統計for(int x = 0; x < n; x++){for(int y = 0; y < m; y++){if((i >> x) & 1)//當前行被選擇{sum += a[x][y];}else{col[y] += a[x][y];  }}}sort(col,col+m,cmp);for(int j = 0; j <(k-cnt); j++){sum += col[j];}answer = max(answer,sum);}cout << answer << endl;return 0;
}

1.calcnt的作用是找到二進制枚舉方案中對行進行了幾次選取，也就是求出i的二進制表示中有多少個1

2.cmp是傳遞給sort的仿函數，用于將排序變為降序

矩陣消除游戲