洛谷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…...
AI模型评估指标:InstantID在各项基准测试中的表现
AI模型评估指标:InstantID在各项基准测试中的表现 【免费下载链接】InstantID 项目地址: https://ai.gitcode.com/hf_mirrors/InstantX/InstantID InstantID作为一款领先的AI模型,在多项基准测试中展现出卓越性能。本文将深入解析其在各项评估指…...
告别“炼丹”:用ReVeal的GGNN+Triplet Loss实战代码漏洞检测,我踩过的坑你别踩
从理论到实践:ReVeal漏洞检测模型落地中的关键挑战与解决方案 在代码安全领域,深度学习技术的应用正经历着从实验室研究到工业落地的关键转折期。ReVeal作为近年来备受关注的漏洞检测框架,其结合GGNN图神经网络与Triplet Loss的创新设计&…...
化整为零、分而治之、异步编排:一文读懂现代并发的底层心法
LongAdder:化整为零,热点分散 在Java多线程编程中,原子变量(如AtomicLong)通过CAS操作实现线程安全的累加。然而,在高并发场景下,大量线程争抢同一原子变量会引发严重的缓存一致性问题。…...
Windows平台OpenClaw部署:百川2-13B-4bits量化版调用详解
Windows平台OpenClaw部署:百川2-13B-4bits量化版调用详解 1. 为什么选择这个组合? 去年冬天,当我第一次尝试在Windows笔记本上部署本地AI助手时,遇到了显存不足的难题。我的GTX 3060显卡根本无法承载常规的13B模型,直…...
SEO优化对网站收录有什么作用
SEO优化对网站收录有什么作用 在当今互联网信息爆炸的时代,网站的收录问题显得尤为重要。SEO优化对于网站的收录有着至关重要的作用,无论是对于新开的网站还是已经运营一段时间的网站,优化都能为其带来更多的流量和潜在客户。SEO优化对网站收…...
芯片缺货潮下的应对策略与国产替代方案
1. 芯片缺货潮下的行业现状最近我的一个产品项目中,原本采购价仅5元的ST品牌MCU(微控制器)价格飙升至70元,涨幅高达14倍。这个案例并非个例,而是当前全球半导体行业供应链危机的缩影。作为从业十余年的硬件工程师&…...
StreamlabsArduinoAlerts:嵌入式设备接入Twitch直播事件
1. StreamlabsArduinoAlerts 库深度解析:嵌入式设备接入 Twitch 直播事件的完整实现方案 StreamlabsArduinoAlerts 是一个专为资源受限嵌入式平台设计的轻量级 C 库,其核心目标是让 Arduino、ESP8266、ESP32、Particle 及基于 ATmega/STM32 的 MCU 能够直…...
【Java外部函数性能优化黄金法则】:20年JVM专家亲授JNI/FFM调优的7大致命误区与3步极速修复方案
第一章:Java外部函数优化的演进脉络与性能本质Java平台对外部函数调用(Foreign Function & Memory API,即JEP 454/464/471/472)的演进,标志着JVM从“纯Java世界”迈向系统级互操作的新纪元。其性能本质并非单纯降低…...
如何彻底解决消息撤回难题?RevokeMsgPatcher带来的革新方案
如何彻底解决消息撤回难题?RevokeMsgPatcher带来的革新方案 【免费下载链接】RevokeMsgPatcher :trollface: A hex editor for WeChat/QQ/TIM - PC版微信/QQ/TIM防撤回补丁(我已经看到了,撤回也没用了) 项目地址: https://gitco…...
PvZ Toolkit:植物大战僵尸PC版终极修改器使用指南
PvZ Toolkit:植物大战僵尸PC版终极修改器使用指南 【免费下载链接】pvztoolkit 植物大战僵尸 PC 版综合修改器 项目地址: https://gitcode.com/gh_mirrors/pv/pvztoolkit 还在为植物大战僵尸中资源不足而烦恼吗?PvZ Toolkit是一款专为植物大战僵尸…...
