当前位置: 首页 > news >正文

P1123 取数游戏

取数游戏

题目描述

一个 N × M N\times M N×M 的由非负整数构成的数字矩阵,你需要在其中取出若干个数字,使得取出的任意两个数字不相邻(若一个数字在另外一个数字相邻 8 8 8 个格子中的一个即认为这两个数字相邻),求取出数字和最大是多少。

输入格式

第一行有一个正整数 T T T,表示了有 T T T 组数据。

对于每一组数据,第一行有两个正整数 N N N M M M,表示了数字矩阵为 N N N M M M 列。

接下来 N N N 行,每行 M M M 个非负整数,描述了这个数字矩阵。

输出格式

T T T 行,每行一个非负整数,输出所求得的答案。

样例 #1

样例输入 #1

3
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

样例输出 #1

271
172
99

提示

样例解释

对于第一组数据,取数方式如下:

[ 67 ] 75 63 10 29 29 [ 92 ] 14 [ 21 ] 68 71 56 8 67 [ 91 ] 25 \begin{matrix} [67] & 75 & 63 & 10 \\ 29 & 29 & [92] & 14 \\ [21] & 68 & 71 & 56 \\ 8 & 67 & [91] & 25 \\ \end{matrix} [67]29[21]87529686763[92]71[91]10145625

数据范围及约定

  • 对于 20 % 20\% 20%的数据, 1 ≤ N , ≤ 3 1\le N, \le 3 1N,3
  • 对于 40 % 40\% 40%的数据, 1 ≤ N , M ≤ 4 1\le N,M\le 4 1N,M4
  • 对于 60 % 60\% 60%的数据, 1 ≤ N , ≤ 5 1\le N, \le 5 1N,5
  • 对于 100 % 100\% 100%的数据, 1 ≤ N , M ≤ 6 1\le N, M\le 6 1N,M6 1 ≤ T ≤ 20 1\le T\le 20 1T20
  • 在这里插入图片描述
#include<bits/stdc++.h>
using namespace std;
int t,n,m,ans,maxn;
int a[37];
int vis[7][7];
void dfs(int x)
{if(x>=m*n){maxn=max(maxn,ans);return ;}dfs(x+1);if(vis[x/m+1][x%m+1]==0){ans+=a[x];for(int i=x/m;i<=x/m+2;i++){for(int j=x%m;j<=x%m+2;j++)vis[i][j]++;}dfs(x+1);ans-=a[x];for(int i=x/m;i<=x/m+2;i++){for(int j=x%m;j<=x%m+2;j++)vis[i][j]--;}}
}
int main()
{cin>>t;while(t--){cin>>n>>m;for(int i=0;i<n*m;i++)cin>>a[i];memset(vis,0,sizeof vis);dfs(0);cout<<maxn<<endl;maxn=0,ans=0;memset(a,0,sizeof a);}return 0;
}

相关文章:

P1123 取数游戏

取数游戏 题目描述 一个 N M N\times M NM 的由非负整数构成的数字矩阵&#xff0c;你需要在其中取出若干个数字&#xff0c;使得取出的任意两个数字不相邻&#xff08;若一个数字在另外一个数字相邻 8 8 8 个格子中的一个即认为这两个数字相邻&#xff09;&#xff0c;求…...

JavaScript高级:原型与原型链继承方式

在 JavaScript 中&#xff0c;继承是一种重要的概念&#xff0c;它使得对象可以从其他对象继承属性和方法&#xff0c;实现代码的重用和扩展。原型与原型链是 JavaScript 中实现继承的核心机制&#xff0c;虽然听起来有些高深&#xff0c;但我们可以通过通俗易懂的方式来理解它…...

使用vue-grid-layout时 You may need an appropriate loader to handle this file type.

使用vue-grid-layout时 You may need an appropriate loader to handle this file type. node版本不匹配 我的node v14.16.0 vue-gride-layout 需要用 v 2.3.7的版本 卸载后重新安装即可...

C# 2048小游戏核心算法

文章目录 01.程序结构划分02.去零03.合并04.上移05.下移/左移/右移&#xff0c;只是取数据的方向不同06.提高可读性 01.程序结构划分 02.去零 有序向量“唯一化”的思路。 /// <summary>/// 去零/// </summary>/// <param name"row">对于一行或一…...

设计模式(5)代理模式

一、介绍&#xff1a; 【Subject/抽象角色】定义了RealSubject和Proxy的共用接口&#xff0c;这样就可以在任何使用RealSubject的地方都可以使用Proxy 【RealSubject/真实角色】定义Proxy所代表的真实实体 【Proxy/代理角色】保存一个引用使得代理可以访问实体&#xff0c;并…...

Django配置(部署环境较乱,暂时启用)

django配置 web服务器中部署项目及WSGI简介 web服务器 WSGI 在IIS中部署django项目 安装 wfastcgi &#xff1a;pip install wfastcgi安装IIS&#xff1a; 以上选择项勾选后确定 将CGI文件复制到项目中&#xff0c; 将项目复制到IIS默认目录中 部署IIS 添加变量信息如下…...

【设计模式】桥接模式

桥接&#xff08;Bridge&#xff09;是用于把抽象化与实现化解耦&#xff0c;使得二者可以独立变化。这种类型的设计模式属于结构型模式&#xff0c;它通过提供抽象化和实现化之间的桥接结构&#xff0c;来实现二者的解耦。 这种模式涉及到一个作为桥接的接口&#xff0c;使得…...

ol问题总结二

一、加载坐标系是4326格式的&#xff0c;使用wfsServer发布的服务&#xff0c;图层加载失败&#xff1b;坐标系是3857格式的。图层加载正常 原因&#xff1a;4326格式的&#xff0c;发布出来的&#xff0c;经纬度是颠倒的 解决方案一&#xff1a;将经纬度进行反转 <templa…...

批量打印-----jsPDF将图片转为pdf,并合并pdf

安装依赖并引入 import jsPDF from jspdf; import { PDFDocument, } from pdf-lib;注意一、 使用jspdf将图片&#xff08;jpg/jpeg/png/bmp&#xff09;转pdf&#xff08;记为pdfA&#xff09;&#xff0c;得到的pdf&#xff08;pdfA&#xff09;和需要合并的pdf(记为pdfB)类…...

【Git】版本控制器详解之git的概念和基本使用

版本控制器git 初始Gitgit的安装git的基本使用初始化本地仓库配置本地仓库三区协作添加---add修改文件--status|diff版本回退--reset撤销修改删除文件 初始Git 为了能够更⽅便我们管理不同版本的⽂件&#xff0c;便有了版本控制器。所谓的版本控制器&#xff0c;就是⼀个可以记…...

C语言 棱形图案

目录 一、问题分析 上部分&#xff1a; 下部分&#xff1a; 二、代码演示 一、问题分析 如上图所示&#xff0c;我们可以将棱形进行拆解&#xff0c;分为上下两个部分。 上部分&#xff1a; 通过观察&#xff0c;我们得到 单边空格数 上半部分总行数 - 行数 - 1 …...

在idea使用GitHub账号、Copilot异常

登录GitHub显示这样的信息&#xff1a; Invalid authentication data.Connection refused: connect Failed to initiate the GitHub login process. Please try again. 修改hosts&#xff08;C:\Windows\System32\drivers\etc\hosts&#xff09;&#xff0c;添加以下参数即可…...

面试热题(反转字符串中的单词)

给你一个字符串 s &#xff0c;请你反转字符串中 单词 的顺序。 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。 注意&#xff1a;输入字符串 s中可能会存在前导空格、尾随空格…...

Stable Diffusion WebUI 从零基础到入门

本文主要介绍Stable Diffusion WebUI的实际操作方法&#xff0c;涵盖prompt推导、lora模型、vae模型和controlNet应用等内容&#xff0c;并给出了可操作的文生图、图生图实战示例。适合对Stable Diffusion感兴趣&#xff0c;但又对Stable Diffusion WebUI使用感到困惑的同学&am…...

【uniapp】一文读懂app端安装包升级

一、前言 首先&#xff0c;在app端开发上线的过程中&#xff0c;会面临一个问题&#xff0c;就是关于app端的版本升级的问题。如果不做相关处理来引导用户的话&#xff0c;那么app就会出现版本没有更新出现的各种问题&#xff0c;我们常见的有在线升级和去指定地址下载安装两种…...

【算法题】2518. 好分区的数目

题目&#xff1a; 给你一个正整数数组 nums 和一个整数 k 。 分区 的定义是&#xff1a;将数组划分成两个有序的 组 &#xff0c;并满足每个元素 恰好 存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k &#xff0c;则认为分区是一个好分区。 返回 不同 的好分区的…...

编写守护进程

守护进程是一个后台进程&#xff0c;当操作系统启动时就可以运行的进程&#xff0c;当操作系统结束时结束的进程&#xff0c;与终端无关。 结果 不想要了就杀死...

stable-diffusion-webui启动No Python at ‘C:\xxx\xxx\python.exe‘

打开webui.bat 把 if not defined VENV_DIR (set "VENV_DIR%~dp0%venv") 中的%~dp0venv改成自己python的安装路径就行获取直接set值即可 如 set VENV_DIRD:\Users\xxx\AppData\Local\Programs\Python\Python310 另外就是直接运行webui-user.bat也可以 如果运行…...

面试热题(合并两个有序列表)

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 合并链表这类型题也是比较经典的题了&#xff0c;因为链表是由指针相互指向而确定位置&#xff0c;所以我们只需要改变某些节点的指针便可以做到对链表进行排序 今天这个方法…...

QT生成Word PDF文档

需求&#xff1a;将软件处理的结果保存为一个报告文档&#xff0c;文档中包含表格、图片、文字&#xff0c;格式为word的.doc和.pdf。生成word是为了便于用户编辑。 开发环境&#xff1a;qt4.8.4vs2010 在qt的官网上对于pdf的操作介绍如下&#xff1a;http://qt-project.org/…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...