题解 | #矩阵消除游戏#

贪心加二进制枚举问题 分析:首先想到的策略就是每次在行和列中选择最大的，然后把这一行或者列置为i，然而这样贪心，每一步的操作都会影响后面的操作，如果想找反例可以将某一行或者某一列取的特别大试试，然而这题如果想这样贪心数据范围给的也太小了，自然就想到了搜索和二进制枚举，这题用二进制枚举来写，将行数转化成二进制然后，枚举每一列然后排个序就可以了

#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
typedef long long LL;
LL n , m , k;
LL  a[N][N];
LL sx[N] , sy[N];
int main()
{
    cin >> n >> m >> k;
    for(int i = 1 ;i <= n;i ++) for(int j = 1 ;j <= m ;j ++) cin >> a[i][j];
    LL  ans = 0;
    if(k >= min(m , n))
    {
        for(int i = 1;i <= n;i ++) 
            for(int j = 1; j<= m; j++) 
                ans += a[i][j];
        cout << ans; return 0;
    }
    else 
    {
          ans = 0;
         LL b[N][N];
            for(int i = 0 ;i < 1 << n ;i ++)
            {
                 for(int k = 1; k <= n; k ++) 
                      for(int j =1 ;j <= m ;j ++) 
                           b[k][j] = a[k][j];
                LL cnt = 0 , res = 0 ;
                for(int j = 0 ;j < n ;j ++) 
                     if(i >> j & 1) 
                     {
                         cnt ++;
                        for(int k = 1 ; k <= m ;k ++) 
                        {
                            res += b[j+1][k]; b[j+1][k] = 0;
                        }
                     }
                if(k < cnt ) continue;
               memset(sy , 0 , sizeof sy);
                for(int i =1 ;i <= n;i ++) 
                     for(int j = 1; j<= m ;j ++) 
                            sy[j] += b[i][j];
                sort(sy + 1 , sy + 1 + m , greater<int>());
                for(int kk = 1; kk <= k - cnt ; kk ++)
                    res += sy[kk];
                ans = max(ans , res);
            }
        cout << ans;
     }
}