【贪心】矩阵消除游戏
矩阵消除游戏矩阵消除游戏题目详情算法原理错误的贪心每次都选当前看起来最好的一行或者⼀列然后选完之后修改原数组继续重复刚刚的操作。反例当 k 2 时如果是贪心的话会选第一列和最后一列。但是最优情况下我们可以把所有的数都选上因此直接上来就贪心不是最优解。直接贪心的错误在于我们每次选完一行或者一列之后会对接下来的行或者列的选择造成影响。因此最优解是先暴力枚举所有行的选法(利用二进制1为选0为不选)在行的选择都确定之后再去贪心的处理列。本题是不需要证明的哈代码实现#include iostream #include algorithm #include cstring using namespace std; const int N 20; int n, m, k; int a[N][N]; int col[N]; // 统计列和 // 统计 x 的二进制表示中 1 的个数 int calc(int x) { int ret 0; while(x) { ret; x - x -x; } return ret; } // 按照值从大到小排序 bool cmp(int a, int b) { return a b; } int main() { cin n m k; for(int i 0; i n; i) for(int j 0; j m; j) cin a[i][j]; int ret 0; // 暴力枚举出行的所有选法 for(int st 0; st (1 n); st) { int cnt calc(st); if(cnt k) continue; // 不合法的状态 memset(col, 0, sizeof col); int sum 0; // 记录当前选法中的和 for(int i 0; i n; i) { for(int j 0; j m; j) { if((st i) 1) sum a[i][j]; else col[j] a[i][j]; } } // 处理列 sort(col, col m, cmp); // 选 k - cnt 列 for(int i 0; i min(k - cnt, m); i) sum col[i];//防止(k - cnt)过大越界访问 ret max(ret, sum); } cout ret endl; return 0; }结语如果觉得有收获欢迎点赞/收藏我们下期见
)
