[算法] 贪心--矩阵消除游戏

文章目录

    • 1. 题意
    • 2. 思路
      • 贪心思路1
      • 思路1并不正确
      • 思路1为什么是错误的?
      • 这道题该如何求解?
      • 枚举思路是超时的!
      • 枚举 + 贪心
    • 3. 编码

今天咱们来分享一道基础的贪心题目 -> 矩阵消除游戏

  对于贪心算法的题目, 我感觉是对于初学者没必要太注重证明过程, 因为这玩意的变数比较大, 还是应该关注在编码和思路上, 在思路上对了就行.

1. 题意

题目描述
  牛妹在玩一个名为矩阵消除的游戏,矩阵的大小是n{n}行m{m}列,第i{i}行第j{j}列的单元格的权值为ai,ja_{i,j},牛妹可以进行k{k}个回合的游戏,在每个回合,牛妹可以选择一行或者选择一列,然后将这一行或者这一列的所有单元格中的权值变为0{0},同时牛妹的分数会加上这一行或者这一列中的所有单元格的权值的和。
牛妹想最大化她的得分,球球你帮帮她吧!

输入描述:
第一行三个整数n,m,k{n,m,k}
接下来n{n}行每行m{m}个整数表示矩阵中各个单元格的权值。

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

示例1
输入

输出
414

1011102
12021
1008100

备注:

2. 思路

贪心思路1

  思路1: 这个题目一上来如果盲才的话, 直觉上是统计一下每行之和和每列之和, 然后找出最大的数来, 加到ret上, 然后把对应的数变成0, 再找出第二大的列和/行和, 以此重复操作, 直到k次/该数组所有行列已经被全部清0.
  我们以示例1举个例子(最下一行为每列的和, 最右边一列为每行之和):

1011102204
12021204
1008100208
202211203

然后, 我们第一步选211对吧? ret += 211然后就会变成下面:

1010102203
1012
1000100200
2020203

然后我们再选203, ret += 204, ret = 414, 我们可以看到:

0000
1012
1000100200
2020203

在这里插入图片描述

总共选择了两次, 因此我们的结果就是414.

思路1并不正确

显然, 这个思路1并不正确, 因为我们可以轻松举出反例: 其中k = 2

10091
000
10080

如果按照贪心来求, 会先选择100 + 100, 然后清零操作:

091
000
080

然后再选择 9 + 1

000
000
080

所以贪心求出来的结果是多少呢? 210.
但是如果我们直接找的是第一行和第三行呢? sum = 218.

因此, 我们上面的贪心解是错误的!

思路1为什么是错误的?

  我们继续以我们举的反例来说, 只能说是因为贪心算法目光短视并且第一步选啥会对第二步所选产生影响所导致的!

10091
000
10080

为什么思路1是错误的?

  • 因为贪心是目光狭隘的, 只看得到当前这一步.
  • 因为这个题目行会影响列, 列会影响行, 行列之间强关联.

这道题该如何求解?

  我们的思路1只能说不是完全对, 但是针对大部分情况是对的, 关键问题在于行列之间强关联 + 贪心算法鼠目寸光, 所以, 我们需要使行列解耦合.

如何解耦合??? -> 很简单, 枚举啊!

枚举思路是超时的!

  如果用暴力求解: 假设n和m都不大,比如都是20左右,那么总共有40个元素(行+列),每个可以选择或不选,但总选择的数量不超过k。这时候,枚举所有可能的组合,总共有C(40,0)+C(40,1)+…+C(40,k)种可能。当k=20时,这大约是组合数的总和,可能达到1e12,这显然不可行。

  显然, 这样去做的话可以解耦, 因为行和列的关系从暴力的角度来说就不存在啥制约关系了, 因为所有可能情况我们都会计算嘛, 压根就不会担心选哪行哪列的问题! 但是缺点是时间复杂度上来了!

  那我们可不可以有一种算法比思路1效率上差点, 但是可以解除行列耦合, 比暴力效率高点呢? 我们尝试把这两种思路结合一下:

枚举 + 贪心

  既然⾏的选择会影响列,那我们⼲脆直接把「所有⾏的选法」枚举出来,然后针对「每⼀种⾏的选法」再处理列,这样就会把「所有情况」都考虑进去。
因此,最优解是先暴⼒枚举所有⾏的选法,在⾏的选择都确定之后,再去贪⼼的处理列。

  这样的话, 因为我们枚举了行, 针对每一种行的情况, 贪心只需要贪列的部分就可以了, 因此行列就不会影响贪心选择了, 而且效率上, 因为列的部分是贪心出来的, 所以效率上也得到了提高!

3. 编码

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int n, m, k;
const int N = 20;
int nums[N][N];
int col[N];bool cmp(int a, int b)
{return a > b;
}int calc(int x)
{int ret = 0;while(x){ret += 1;x -= (x & -x);}return ret;
}int main()
{int ret = 0;// 读入数据cin >> n >> m >> k;for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)cin >> nums[i][j];// 二进制枚举for(int stat = 0; stat < (1 << n); stat++){int size = calc(stat);if(size > 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(stat & (1 << i)) sum += nums[i][j];else col[j] += nums[i][j];}}sort(col, col + m, cmp);int take = min(k - size, m); // [细节]: 有没有可能k - size > m呢? 也就是会越界访问??? for(int i = 0; i < take; i++) sum += col[i];ret = max(ret, sum);}cout << ret << endl;return 0;
}

编码细节: 如果k > m + n, 则可能会导致贪心算法加和的时候会越界, 因此我们需要额外判断一下!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/35018.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

数学——A. K-divisible Sum + D. Exam in MAC

A. K-divisible Sum 题目&#xff1a; 思路&#xff1a; 以下 “[xxx]” 符号均代表向上取整 我们假设总和是sum&#xff0c;那么就有sum k * cnt 要想最大值最小&#xff0c;肯定是要让sum尽可能小&#xff0c;这样每个元素都能变小 最小情况是 sum 恰好等于 n 时&#…

Docker 》》Docker Compose 》》network 网络 compose

docker 默认的网络 三种模式 # 列出所有当前主机上或Swarm集群上的网络 docker network ls#查看网络详情 docker network inspect network名称# 清除未使用的docker网络 docker network prune -f# 创建网络 ocker network create -d bridge 网络名称 docker network create –s…

RabbitMQ延迟消息

文章目录 延迟消息死信交换机延迟消息延迟消息应用场景 延迟消息 生产者在发送消息的时候指定一个时间&#xff0c;消费者不会立即收到该消息&#xff0c;而是在指定时间之后才收到消息&#xff0c;这就是延迟消息。 比如说这么一个场景&#xff0c;用户下单后将商品库存进行…

phpstudy+phpstorm+xdebug【学习笔记】

配置PHPStudy 配置PHPSTORM phpstorm选择PHP版本 配置DEBUG 设置服务器 编辑配置 学习参考链接&#xff1a;&#xff1a;https://blog.csdn.net/m0_60571842/article/details/133246064

58.Harmonyos NEXT 图片预览组件架构设计与实现原理

温馨提示&#xff1a;本篇博客的详细代码已发布到 git : https://gitcode.com/nutpi/HarmonyosNext 可以下载运行哦&#xff01; Harmonyos NEXT 图片预览组件架构设计与实现原理 文章目录 Harmonyos NEXT 图片预览组件架构设计与实现原理效果预览一、组件架构概述1. 核心组件层…

Android 手机启动过程

梳理 为了梳理思路&#xff0c;笔者画了一幅关于 Android 手机启动的过程图片内容纯属个人见解&#xff0c;如有错误&#xff0c;欢迎各位指正

Chat-TTS-UI:文字转语音 - 本地部署方案

Chat-TTS-UI 是一个基于 ChatTTS 模型的本地网页界面,专为满足用户在信息过载时代轻松获取大量文字信息的需求而设计。它支持中英文混合输入、多种音色选择,并提供 API 接口,方便开发者集成到其他应用中。其简洁易用的网页界面、细粒度控制以及 GPU 加速等高级功能,使其广泛…

11. Pandas :操作Excel文件(Excel报表的案例研究)

从一个装有各种 Excel 文件的文件夹开始&#xff0c;这些文件需要被整合到 Excel 报表中。 它们包含了虚构的电信运营商在全美各营业厅的套餐&#xff08;金、银、铜&#xff09;销售情况。每个月有两个文件&#xff0c;子文件夹 new 中的是新用户&#xff0c;子文件夹 existin…

一周学会Flask3 Python Web开发-SQLAlchemy添加数据操作-班级模块

锋哥原创的Flask3 Python Web开发 Flask3视频教程&#xff1a; 2025版 Flask3 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili SQLAlchemy提供session.add()方法添加model实体数据&#xff0c;以及提供session.commit()提交事务。 首先list.html加一个添…

大型语言模型与强化学习的融合:迈向通用人工智能的新范式——基于基础复现的实验平台构建

1. 引言 大型语言模型&#xff08;LLM&#xff09;在自然语言处理领域的突破&#xff0c;展现了强大的知识存储、推理和生成能力&#xff0c;为人工智能带来了新的可能性。强化学习&#xff08;RL&#xff09;作为一种通过与环境交互学习最优策略的方法&#xff0c;在智能体训…

Axure大屏可视化原型模板及素材:数据可视化的高效解决方案

数据可视化已成为企业决策、运营分析、市场洞察的重要工具。数据可视化大屏&#xff0c;作为数据展示和交互的直观平台&#xff0c;能够实时呈现关键数据&#xff0c;帮助企业快速做出决策。Axure作为原型设计领域的领先工具&#xff0c;以其丰富的组件库、强大的交互设计能力和…

图片填充容器,如何描述

【图片需要完全填充/拉伸以适应容器尺寸&#xff0c;不保持原始比例&#xff0c;使用 object-fit: fill 属性实现】 效果&#xff1a; 代码案例&#xff1a; <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8">&l…

缓存和客户端数据存储体系(Ark Data Kit)--- 应用数据持久化(首选项持久化、K-V、关系型数据库)持续更新中...

Core File Kit做怎删改查操作不便&#xff0c;用Ark Data Kit。 功能介绍 ArkData &#xff08;方舟数据管理&#xff09;为开发者提供数据存储、数据管理和数据同步能力&#xff0c;比如联系人应用数据可以保存到数据库中&#xff0c;提供数据库的安全、可靠以及共享访问等管…

RUOYI框架在实际项目中的应用三:Ruoyi微服务版本-RuoYi-Cloud

如需观看Ruoyi框架的整体介绍&#xff0c;请移步&#xff1a;RUOYI框架在实际项目中的应用一&#xff1a;ruoyi简介 一、Ruoyi微服务版本-Ruoyi微服务版本 1、官方资料 1&#xff1a;代码地址&#xff1a;https://gitee.com/y_project/RuoYi-Cloud.git 2&#xff1a;文档介绍…

windbg集成python环境(pykd)

背景: 调试FPU指令过程时&#xff0c;需要一直跟踪FPU Status寄存器TOP字段(ST寄存器对应的BC寄存器)&#xff0c;TOP寄存器位于FPU Status[13:11]&#xff0c;这种转换过程并非一目了然(如下图)&#xff1a; [Disassembly窗口fld指令执行后&#xff0c;Registers窗口中fpsw的…

微信小程序threejs三维开发

微信小程序threejs开发 import * as THREE from three; const { performance, document, window, HTMLCanvasElement, requestAnimationFrame, cancelAnimationFrame, core, Event, Event0 } THREE .DHTML import Stats from three/examples/jsm/libs/stats.module.js; im…

【算法】双指针、递归与回溯、排序、查找

⭐️个人主页&#xff1a;小羊 ⭐️所属专栏&#xff1a;Linux 很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~ 目录 持续更新中...1、双指针移动零复写零快乐数长度最小的子数组dd爱框框 2、递归与回溯3、排序算法4、查找算法 持续更新中… 1、双指…

How to install cangjie on Linux mint 22.1

概述 仓颉编程语言是一款面向全场景智能的新一代编程语言&#xff0c;主打原生智能化、天生全场景、高性能、强安全。主要应用于鸿蒙原生应用及服务应用等场景中&#xff0c;为开发者提供良好的编程体验。 今天&#xff0c;我们介绍一下仓颉语言在Linux mint 22.1上的安装。 …

杰理可视化SDK-手机三方通话控制

杰理可视化SDK-手机三方通话控制 手机三方通话功能杰理SDK三方通话控制SDK三方通话状态获取SDK三方通话处理 手机三方通话功能是手机常用的功能之一。本篇文章简单介绍了杰理可视化SDK在蓝牙耳机应用中&#xff0c;当手机存在三方通话来电或正在进行三方通话时&#xff0c;蓝牙…

【二分算法】-- 寻找旋转排序数组中的最小值

文章目录 1. 题目2. 题目解析3. 代码 1. 题目 在线oj 2. 题目解析 解法一&#xff1a;暴力查找最小值 时间复杂度&#xff1a;0(N) 解法二&#xff1a;二分查找算法 【二段性】&#xff1a; A~B&#xff1a;nums[i] > nums[i 1] C~D&#xff1a;nums[i] < nums[i…