矩阵消除游戏

灵感来源https://blog.nowcoder.net/n/6bcd181f88684b9a85c359f84a44539e
矩阵消除游戏

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 20;

int n, m, k;
int a[N][N];
ll sh[N], sl[N], res = 0;
bool st[N];

int deal(int x) {
    memset(st, 0, sizeof st);
    int cnt = 0, i = 1;
    while(x) {
        if(x & 1) {
            cnt++;
            st[i] = true;
        }
        i++;
        x >>= 1;
    }    
    return cnt;
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            sh[i] += a[i][j];
        }
    if(k > n) k = n;          
    if(k > m) k = m;
    int tmp = (1 << n) - 1;
    for(int i = 0; i <= tmp; i++) {
        int numh = deal(i);
        int numl = k - numh;
        if(numl > m || numl < 0) continue;
        ll sum = 0;
        for(int i = 1; i <= n; i++) if(st[i]) sum += sh[i];
        memset(sl, 0, sizeof sl);
        for(int j = 1; j <= n; j++)
            for(int k = 1; k <= m; k++) {
                if(!st[j]) sl[k] += a[j][k];
            }
        sort(sl + 1, sl + 1 + m);
        for(int j = 1, k = m; j <= numl; j++, k--) sum +=sl[k];
        res = max(res, sum);
    } 
    printf("%lld\n", res);
    return 0;
} 

这题范围为15 应该是暴力枚举
不能用贪心的想法去做这到题，是因为选完最优的状态之后会对后面的最优状态产生影响