NC200190 矩阵消除游戏

错误思路：
    每回合选择之前，先计算每行每列的权值和，然后选最大的那一行或列。
    按这个思路来写，如果正好是先选了一堆行再选一堆列，或者是先选一堆列再选一堆行，那么不会出现问题。但如果是选了行，选了列，后面又开始选行了，那么答案就会出问题，因为你的选列行为对后面的选行造成了影响。（不是很好说，但能举出很多反例）

这里引用一下大佬们的题解：

因为你的每次选择，选一列也好选一行也好，会对后面的选择造成影响，且不同的选择造成的影响是不一样的，你这次先选了最好的一行（列）有可能就会使得后面能选的变少，你没选最好的一行（列）后面的机会却更多，这就是不满足无后效性，就好像装箱问题：给你一个体积为V的箱子，再给你若干件体积不同的物品，希望选一些物品尽量装满，你会上来就选择最大的吗？我们会很容易的想到，也许拼两个小的比装一个大的更好。对于做个题其实也一样，你选了最大的，后面选的就少了……
链接

不对的理由是：因为行选取了最大的之后，会对列产生影响，因为用到了列的数据嘛。
但是如果只对行或列贪心的话就不会产生这种问题了，因为互相之间没有干扰。 链接

正确的思路：
    在上面我提到如果正好是先选了一堆行再选一堆列，或者是先选一堆列再选一堆行，那么不会出现问题，因为选完了行以后再去选列，每次选取不会对其他的列造成影响。

    所以我们就可以用枚举的方法，先枚举每一种对行选取的情况，然后再去选剩下的最大的那几列就可以了。
    这里对行的选取情况确定了以后，要选取的列的个数也确定了，每一个列的权值和也是固定不变的，所以只需要对行进行枚举，枚举以后对列的权值和排序以后直接从最大的开始选即可。（如果每次又对列进行枚举，会浪费大量时间）

    可以再优化一下，如果每一次对行枚举都要重新计算行的权值和会重复很多操作，所以可以直接在输入矩阵时计算每行的权值和。但是对每列的权值和的计算必须在把行选择完以后进行

*把DEBUG改成1会输出一些我调试时留下的垃圾

#include <iostream>
#include <memory.h>
#include <algorithm>

#define DEBUG 0
using namespace std;

int main() {
    int n, m;
    int k;  //进行k个回合的游戏
    long long tempSum, maxSum = 0;
    cin >> n >> m >> k;
    long long matrix[n + 1][m + 1];   //每一行最后一个元素这行元素的总和，列同理
    //矩阵初始化全部为0
    memset(matrix, 0, sizeof(matrix));
    //读入矩阵并且计算前缀和
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> matrix[i][j];
            matrix[i][m] += matrix[i][j];
        }
    }

    //如果k能把整个矩阵选完，直接输出整个矩阵的和
    if (k >= n || k >= m) {
        for (int i = 0; i < n; ++i) {
            maxSum += matrix[i][m];
        }
        cout << maxSum;
        return 0;
    }
    //k不能把整个矩阵选完，对选择情况进行遍历
    //先确定行的选择情况，行选择完以后再选列
    for (int row = 0; row < ((1 << n) - 1); ++row) {
        int rowPick = 0;  //有多少行被选择
        for (int i = 0; i < n; ++i) {
            if (row & (1 << i))rowPick++;
        }
        if (rowPick > k)continue; //如果选择的行数大于实际行数则不合法
        tempSum = 0;

        //先遍历行
        if (DEBUG) {
            cout << "所选行： ";
        }
        //把选中的行的权值和加到tempSum
        for (int i = 0; i < n; ++i) {
            if ((1 << (n - i - 1)) & row) {
                tempSum += matrix[i][m];
                if (DEBUG)cout << i + 1 << " ";
            }
        }
        if (DEBUG)cout << "\n选完行以后的tempSum: " << tempSum << endl;
        //计算每一列剩下元素的总和
        for (int i = 0; i < m; ++i) {
            matrix[n][i] = 0; //先清理一下
            for (int j = 0; j < n; ++j) {
                if (!((1 << (n - j - 1)) & row)) {
                    matrix[n][i] += matrix[j][i];
                }
            }
        }

        if (DEBUG) {
            cout << "矩阵：" << endl;
            for (int i = 0; i < n + 1; ++i) {
                for (int j = 0; j < m + 1; ++j) {
                    cout << matrix[i][j] << " ";
                }
                cout << endl;
            }
        }

        //对每一列剩下元素的总和进行排序，只选最大的那几列
        sort(matrix[n], matrix[n] + m, greater<>());

        int columnPick = k - rowPick;   //有多少列被选择
        if (DEBUG)cout << "columnPick: " << columnPick << endl;
        for (int i = 0; i < columnPick; ++i) {
            tempSum += matrix[n][i];
        }
        if (DEBUG)cout << "选完列以后的tempSum: " << tempSum << endl << endl;
        maxSum = max(maxSum, tempSum);

    }
    cout << maxSum;
}