我們第一次想到的貪心策略一定是找出和最大的行或者列來刪除，每次都更新行和列

比如如圖這種情況，這種情況就不如直接刪除兩行的多，所以本貪心策略有誤

so我們可以枚舉選的行的情況，然后再貪心的選擇列和最大的列來做

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,k;
typedef long long ll;
const int N = 20;int sum;int col[N];
int a[N][N];int calc(int x)
{int ret = 0;while(x){ret++;x -= x & -x; }return ret;
}bool cmp(int x,int y)
{return x>y;
}
int ret;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 st = 0;st<(1<<n);st++){memset(col,0,sizeof(col));sum = 0;if(calc(st)>k) continue;for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){if((st>>i)&1) sum+=a[i][j];else col[j]+=a[i][j];}}sort(col,col+m,cmp);int tmp = k-calc(st);for(int i = 0;i<tmp;i++){sum+=col[i];}ret = max(ret,sum);}cout << ret; return 0;
}

這樣寫是有bug的，我們選列的時候有可能會越界

因為我們的k最高是n*m，假如不選行，全選列，列是不夠選的啊，我們應該對col的遍歷范圍做點限制，不能超過m

正確代碼√

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,k;
typedef long long ll;
const int N = 20;
int a[N][N];
int sum;
int col[N];int calc(int x)
{int ret = 0;while(x){ret++;x -= x & -x; }return ret;
}bool cmp(int x,int y)
{return x>y;
}
int ret;
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 st = 0;st<(1<<n);st++){memset(col,0,sizeof(col));sum = 0;if(calc(st)>k) continue;for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){if((st>>i)&1) sum+=a[i][j];else col[j]+=a[i][j];}}sort(col,col+m,cmp);int tmp = k-calc(st);for(int i = 0;i<min(tmp,m);i++){sum+=col[i];}ret = max(ret,sum);}cout << ret; return 0;
}