【练习】矩阵消除游戏

题目

题目描述：

牛妹在玩一个名为矩阵消除的游戏，矩阵的大小是n行m列，第i行第j列的单元格的权值为a_ij。

牛妹可以进行k个回合的游戏，在每个回合，牛妹可以选择一行或者选择一列。

然后将这一行或者这一列的所有单元格中的权值变为{0}0，同时牛妹的分数会加上这一行或者这一列中的所有单元格的权值的和。

牛妹想最大化她的得分，球球你帮帮她吧！

输入描述：
第一行三个整数n,m,k。

接下来n行每行m个整数表示矩阵中各个单元格的权值。

输出描述：
输出一个整数表示牛妹能获得的最大分数。

解析

这道题我们要选最大值，当然可以想到这是一道贪心的题目。

但是贪心方法值得我们考究。因为我理所当然的贪错了。

我的贪心策略：

首先，我们要贪心贪出最大的来对吧，那我们当然就会想到：从最大的开始选咯。
所以每次从行和列中选出一个最大的来进行行列删除。
删除k次就行了。

错误原因：

根本的错误就是我理所当然的认为我的贪心策略是对的了。其实取个反例就知道不对了。
不对的理由是：因为行选取了最大的之后，会对列产生影响，因为用到了列的数据嘛。
但是如果只对行或列贪心的话就不会产生这种问题了，因为互相之间没有干扰。

新的贪心策略：

我们上面也已经讲到了新的贪心策略：就是只对行或列进行贪心！那另外的一个（行或列）呢？就枚举呗！
其实我一开始都不明白为什么数据会这么小，是不是打错了，居然只有15。原来是枚举用的（其实很多时候，数据就是提示）。
所以这里我们就用二进制枚举+贪心。

咋操作呢？

二进制枚举和贪心我就不详细讲解了。
我们就枚举行的每一种情况，枚举的时候，二进制1的数量就是选取行的数量，二进制1的位置就是选出行的位置。
然后算出对应的列和与选取的列的数量（为啥要算，每次不一样吗？确实不一样，因为每次删除的行不一样呀）。给列排个序，按照从大到小选就好了。

看代码咯：

首先输入数据并初始化我们的行和。
然后特判一下K是不是比行和列还大，还大确实就和取满是一样的了。
接下来就是外循环二进制枚举了。
然后里面就先得到当前行的选取情况，和行选取数。并特判不存在的情况。
然后求出这种情况下，每一列的列和。
给列和排个序，选最大的几个（几个就是指：总选取数 - 行选取数）。
最后每个最大的比较一下，选出二进制枚举里面每一种可能中最大的，输出就好了。
看代码咯~

WA代码

#include <iostream>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 17;
int n, m, k;
int mp[MAX][MAX], sum[MAX][2];//地图+行列前缀和(0为行，1为列)
//全局变量区

int main() {
    IOS;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];
    //地图初始化
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            sum[i][0] += mp[i][j];//行前缀和初始化
            sum[j][1] += mp[i][j];//列前缀和初始化
        }
    //前缀和初始化
    int ans = 0;//计算删除总和
    for (int i = 1; i <= k; i++) {
        int pos = 1, flag = 0;
        for (int j = 1; j <= n; j++)
            if (sum[pos][flag] < sum[j][0]){
                pos = j; flag = 0;
            }
        //查找行最大
        for (int j = 1; j <= m; j++)
            if (sum[pos][flag] < sum[j][1]){
                pos = j; flag = 1;
            }
        //再对比查找列最大
        ans += sum[pos][flag];
        //把该行的值加到答案里面
        if (flag)
            for (int j = 1; j <= m; j++) {
                sum[j][0] -= mp[j][pos];
                mp[j][pos] = 0;
            }
        else
            for (int j = 1; j <= n; j++) {
                sum[j][1] -= mp[pos][j];  
                mp[pos][j] = 0;
            }
        //将这(行/列)在其他(列/行)前缀和中占有的大小减掉
        sum[pos][flag] = 0; 
        //删掉该(行/列)
    }
    cout << ans << endl;
    return 0;
}
//函数区

AC代码

#include <iostream>
#include <algorithm>
#include <string.h>
#include <bitset>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 17;
int n, m, k;
int mp[MAX][MAX], row[MAX], column[MAX];//地图+行列前缀和(0为行，1为列)
bitset<17> flag;
//全局变量区

int calc(int x);//计算选择列的数量，并标记到数组里面
//函数预定义区

int main() {
    IOS;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++){
            cin >> mp[i][j];
            row[i] += mp[i][j];
        }
    //地图初始化，前缀和初始化
    if (k > n) k = n;
    if (k > m) k = m;
    int ans = 0;//计算删除总和
    int len = (1 << n) - 1;//行的二进制枚举
    for (int T = 0; T <= len; T++) {
        int num = calc(T);
        int num_column = k - num;
        if (num_column > m || num_column < 0) continue;
        //用列的数量判断不存在的情况
        int sum = 0;//求这种情况的和
        for (int i = 1; i <= n; i++)
            if (flag[i]) sum += row[i];
        //统计把列拿出来的和
        memset(column, 0, sizeof column);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (!flag[i]) column[j] += mp[i][j];
        //初始化列的情况
        sort(column + 1, column + 1 + n, greater<int>());
        //排个序
        for (int i = 1; i <= num_column; i++)
            sum += column[i];
        //统计最大的num_column列的数
        ans = max(ans, sum);
    }
    cout << ans << endl;
    return 0;
}
int calc(int x) {
    flag.reset();
    int cnt = 0;
    int i = 1;
    while (x) {
        if (x & 1) {
            cnt++;
            flag[i] = 1;
        }
        x >>= 1;
        i++;
    }
    return cnt;
}
//函数区