矩阵消除游戏

题意

一个矩阵，每次可以消除一行或者一列，问最大可以消除的和是多少。

分析

由于矩阵比较小，所以我们可以先枚举消去了哪些行，之后贪心的消去剩下的列（也就是选择列的和更大的），可以利用 dfs 实现。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 20;
const int M = 1e9+7;
int n,m,k,ans;

int a[maxn][maxn],b[maxn][maxn],c[maxn];

void dfs(int u,int sum,int pre)
{
    if(u > k) return;

    for(int j = 1; j <= m; j++) 
    {   
        c[j] = 0;
        for(int i = 1; i <= n; i++) 
        {
            c[j] += b[i][j];
        }
    }
    sort(c+1,c+1+m,greater<int>());
    int tmp = sum;
    for(int i = 1; i <= k-u; i++) tmp += c[i];
    ans = max(ans,tmp);

    for(int i = pre+1; i <= n; i++)
    {   
        int res = 0;
        for(int j = 1; j <= m; j++) 
        {
            res += b[i][j];
            b[i][j] = 0;
        }
        dfs(u+1,sum+res,i);
        for(int j = 1; j <= m; j++) b[i][j] = a[i][j];
    }
}

signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m>>k;
    int sum = 0;
    for(int i = 1; i <= n; i++) 
    {
        for(int j = 1; j <= m; j++) 
        {
            cin>>a[i][j];
            sum += a[i][j];
            b[i][j] = a[i][j];
        }
    }
    if(k >= n || k >= m) 
    {
        cout<<sum<<endl;
    }
    else
    {
        dfs(0,0,0);
        cout<<ans<<endl;
    }
    return 0;
}