洛谷P1123 取数游戏(C++)(DFS)
目录
1.题目
题目描述
输入格式
输出格式
输入输出样例
说明/提示
2.AC
1.题目
题目描述
一个N \times MN×M的由非负整数构成的数字矩阵,你需要在其中取出若干个数字,使得取出的任意两个数字不相邻(若一个数字在另外一个数字相邻88个格子中的一个即认为这两个数字相邻),求取出数字和最大是多少。
输入格式
第1行有一个正整数TT,表示了有TT组数据。
对于每一组数据,第一行有两个正整数NN和MM,表示了数字矩阵为NN行MM列。
接下来NN行,每行MM个非负整数,描述了这个数字矩阵。
输出格式
TT行,每行一个非负整数,输出所求得的答案。
输入输出样例
输入 #13
4 4
67 75 63 10
29 29 92 14
21 68 71 56
8 67 91 25
2 3
87 70 85
10 3 17
3 3
1 1 1
1 99 1
1 1 1输出 #1271
172
99
说明/提示
对于第1组数据,取数方式如下:
[67] 75 63 10
29 29 [92] 14
[21] 68 71 56
8 67 [91] 25
对于20\%20%的数据,N, M≤3N,M≤3;
对于40\%40%的数据,N,M≤4N,M≤4;
对于60\%60%的数据,N, M≤5N,M≤5;
对于100\%100%的数据,N, M≤6,T≤20N,M≤6,T≤20。
2.AC
#include <iostream>
#include <string.h>
using namespace std;int n, m, ans;
int a[10][10], v[10][10];
int tx[8] = {0,1,1,1,0,-1,-1,-1}, ty[8] = {1,1,0,-1,-1,-1,0,1};int f1(int cx,int cy) {v[cx][cy]++;for (int i = 0; i < 8; i++) {int x = cx + tx[i];int y = cy + ty[i];if (x < 0 || y < 0 || x >= n || y >= m) continue;v[x][y]++;}
}int f2(int cx,int cy) {v[cx][cy]--;for (int i = 0; i < 8; i++) {int x = cx + tx[i];int y = cy + ty[i];if (x < 0 || y < 0 || x >= n || y >= m) continue;v[x][y]--;}
}int dfs (int cx, int cy, int sum) {if (cy == m) {cx++;cy = 0;}if (cx == n) {ans = max(ans,sum);return 0;}dfs(cx,cy+1,sum);if (!v[cx][cy]) {f1(cx,cy);dfs(cx,cy+1,sum+a[cx][cy]);f2(cx,cy);}return 0;
}int main()
{int T;cin>>T;while (T--) {ans = 0;memset(v,0,sizeof(v));cin>>n>>m;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin>>a[i][j];} }dfs(0,0,0);cout<<ans<<endl;}return 0;
}
相关文章:
洛谷P1123 取数游戏(C++)(DFS)
目录 1.题目 题目描述 输入格式 输出格式 输入输出样例 说明/提示 2.AC 1.题目 题目描述 一个N \times MNM的由非负整数构成的数字矩阵,你需要在其中取出若干个数字,使得取出的任意两个数字不相邻(若一个数字在另外一个数字相邻88个格…...
Python Qt6快速入门-嵌入PyQtGraph图表
嵌入PyQtGraph 文章目录 嵌入PyQtGraph1、PyQtGraph介绍2、创建PyQtGraph小部件3、绘图样式配置3.1 背景颜色3.2 线条颜色、线宽和样式配置3.3 线标记(Line Markers)3.4 绘制标题3.5 轴标题3.6 图例(Legends)3.7 轴范围限制3.8 绘制多组数据3.10 画布清空4、更新数据5、总结1、…...
Mac电脑_GitHub提交项目至仓库
第一步(准备工作): Mac 电脑自带 git , 无需安装 1. 创建一个项目 demo1 在 github 上 2. 创建 ssh 密钥 打开终端: ssh-keygen -t rsa -C "your_emailyouremail.com" 此处输入两次密码, 直接…...
Android自定义View实现横向的双水波纹进度条
效果图:网上垂直的水波纹进度条很多,但横向的很少,将垂直的水波纹改为水平的还遇到了些麻烦,现在完善后发布出来,希望遇到的人少躺点坑。思路分析整体效果可分为三个,绘制圆角背景和圆角矩形,绘…...
Python 之 Pandas 分组操作详解和缺失数据处理
文章目录一、groupby 分组操作详解1. Groupby 的基本原理2. agg 聚合操作3. transform 转换值4. apply二、pandas 缺失数据处理1. 缺失值类型1.1 np.nan1.2 None1.3 NA 标量2. 缺失值处理2.1 查看缺失值的情形2.2 缺失值的判断2.3 删除缺失值2.4 缺失值填充在开始之前ÿ…...
【人工智能 AI】什么是人工智能? What is Artificial Intelligence
目录 Introduction to Artificial Intelligence人工智能概论 What is Artificial Intelligence? 什么是人工智能?...
17、触发器
文章目录1 触发器概述2 触发器的创建2.1 创建触发器语法2.2 代码举例3 查看、删除触发器3.1 查看触发器3.2 删除触发器4 触发器的优缺点4.1 优点4.2 缺点4.3 注意点尚硅谷MySQL数据库教程-讲师:宋红康 我们缺乏的不是知识,而是学而不厌的态度 在实际开发…...
内核并发消杀器(KCSAN)技术分析
一、KCSAN介绍KCSAN(Kernel Concurrency Sanitizer)是一种动态竞态检测器,它依赖于编译时插装,并使用基于观察点的采样方法来检测竞态,其主要目的是检测数据竞争。KCSAN是一种检测LKMM(Linux内核内存一致性模型)定义的数据竞争(data race)的工…...
蓄水池抽样算法
蓄水池抽样,也称水塘抽样,是随机抽样算法的一种。基本抽样问题有一批数据(假设为一个数组,可以逐个读取),要从中随机抽取一个数字,求抽得的数字下标。常规的抽样方法是,先读取所有的…...
数据结构预算法之买股票最好时机动态规划(可买卖多次)
一.题目二.思路在动规五部曲中,这个区别主要是体现在递推公式上,其他都和上一篇文章思路是一样的。所以我们重点讲一讲递推公式。这里重申一下dp数组的含义:dp[i][0] 表示第i天持有股票所得现金。dp[i][1] 表示第i天不持有股票所得最多现金如…...
华为OD机试真题Java实现【蛇形矩阵】真题+解题思路+代码(20222023)
蛇形矩阵 蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。 例如,当输入5时,应该输出的三角形为: 1 3 6 10 15 2 5 9 14 4 8 13 7 12 11请注意本题含有多组样例输入。 🔥🔥🔥🔥🔥👉👉👉👉👉👉 华为OD机试(Java)真题目录汇总 输入描述:…...
spring Bean的生命周期 IOC
文章目录 1. 基础知识1.1 什么是 IoC ?2. 扩展方法3. 源码入口1. 基础知识 1.1 什么是 IoC ? IoC,控制反转,想必大家都知道,所谓的控制反转,就是把 new 对象的权利交给容器,所有的对象都被容器控制,这就叫所谓的控制反转。 IoC 很好地体现了面向对象设计法则之一 —…...
详解cors跨域
文章目录同源策略cors基本概念cors跨域方式简单请求 simple request非简单请求- 预检请求CORS兼容情况CORS总结同源策略 在以前的一篇博客中有介绍,同源策略是一种安全机制,为了预防某些恶意的行为,限制浏览器从不同源文档和脚本进行交互的行…...
ARM uboot 源码分析7 - uboot的命令体系
一、uboot 命令体系基础 1、使用 uboot 命令 (1) uboot 启动后进入命令行环境下,在此输入命令按回车结束,uboot 会收取这个命令然后解析,然后执行。 2、uboot 命令体系实现代码在哪里 (1) uboot 命令体系的实现代码在 uboot/common/cmd_xx…...
物理服务器与云服务器备份相同吗?
自从云计算兴起以来,服务器备份已经从两阶段的模拟操作演变为由云服务器备份软件执行的复杂的多个过程。但是支持物理服务器和虚拟服务器之间的备份相同吗?主要区别是什么?我们接下来将详细讨论这个问题。 物理服务器与云服务器备份的区别 如果您不熟悉虚拟服务器…...
【Linux】system V共享内存 | 消息队列 | 信号量
🌠 作者:阿亮joy. 🎆专栏:《学会Linux》 🎇 座右铭:每个优秀的人都有一段沉默的时光,那段时光是付出了很多努力却得不到结果的日子,我们把它叫做扎根 目录👉system V共…...
FSC的宣传许可 答疑
【FSC的宣传许可 答疑】问:已经采购了认证产品但没有贴FSC标签,是否可以申请宣传许可?答:不可以。要宣传您采用了FSC认证产品的前提条件之一是产品必须是认证且贴有标签的。如果产品没有贴标,则不可申请宣传许可。您的…...
Leetcode力扣秋招刷题路-0100
从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结 100. 相同的树 给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是…...
协作对象死锁及其解决方案
协作对象死锁及其解决方案 1.前言 在遇到转账等的需要保证线程安全的情况时,我们通常会使用加锁的方式来保证线程安全,但如果无法合理的使用锁,很可能导致死锁。或者有时我们使用线程池来进行资源的使用,如调用数据库࿰…...
良许也成为砖家啦~
大家好,我是良许。 没错,良许成为砖家啦,绝不是口嗨,有图有真相! 有人会说,咦,这明明是严宇啊,跟你良许有啥关系? 额。。老读者应该知道良许的来历—— 鄙人真名严宇&a…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
