【贪心】矩阵消除游戏-北京尧图网络

矩阵消除游戏矩阵消除游戏题目详情算法原理错误的贪心每次都选当前看起来最好的一行或者⼀列然后选完之后修改原数组继续重复刚刚的操作。反例当 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; }结语如果觉得有收获欢迎点赞/收藏我们下期见

【贪心】矩阵消除游戏

相关推荐

【数据库索引标准结构】B+树原理详解与B树对比优势

B2B制造业GEO破局：从AI搜索盲区到推荐首页的系统化方法论

Simulink数据字典：MBD开发中的核心数据管理利器

更多资讯

Tylt面试突击：5个性能优化考点，背下这3段代码稳过

bitcomet官网2026最新

啪啪啪动图开发避坑：3个致命错误与速查手册

GTA5武器秘籍大全避坑指南：3类脚本方案对比选型

3步排查：一文搞懂薛申报错底层逻辑

3分钟吃透昆特算法最佳实践面试突击

今日更新

3个坑点带你一文搞懂55gg小游戏源码

2026最新covar实战：3步搞定环境配置不再卡壳

3个Docker命令避坑指南：手写实现原理

本周精选

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？