P8756 [蓝桥杯 2021 省 AB2] 国际象棋 状压dp统计情况数的一些小理解
目录
- 建议有状压基础再食用:
 - 本题的状态转移方程是
 
- dp代码片:
 - 参考代码
 
建议有状压基础再食用:
n行m列 等价 n列m行 ,因为n比较小,int是32位足够了,我们用比特位统计每一行的状态。
本题的状态转移方程是
dp[h][i][j][num] = (dp[h][i][j][num] + dp[h - 1][j][ii][num - nums[i]])%mod;
 h是行数,i和j表示本行状态和上一行状态,num表示个数。
 nums[i]是情况为 i 时的bit位为1的数目,提前可以统计一下。
 dp的值就是求的情况数。
很难理解,其实我们先不看i 和 j,只看行数和num,这才是dp的样子。
 然后加上i和j状态压缩,就是状压dp了。
(动态规划是有条理的遍历,是全面覆盖的,num所有可以的情况都会遍历。本行i是0也会,所以只有前几行放棋子的,后面全是0也会遍历到的。)
dp代码片:
前一行和本行情况的比特位存在隔2的
 和
 前两行和本行情况的比特位存在隔1的情况直接略去,也就是马会互吃的情况。
//初始化
dp[0][0][0][0] = 1;//0行什么也不放。第一行肯定会摸一下,方案数是1
//for (int h = 1; h <= m; h++)
{for (int i = 0; i < (1ll << n); i++)//本行{for (int j = 0; j < (1ll << n); j++)//前一行{for (int ii = 0; ii < (1ll << n); ii++)//前两行{for (int num = nums[i]; num <= k; num++){if ((i << 2 & j) || (i >> 2 & j))continue;if ((i << 1 & ii) || (i >> 1 & ii))continue;dp[h][i][j][num] = (dp[h][i][j][num] + dp[h - 1][j][ii][num - nums[i]])%mod;}}}}
}
 
参考代码
int n,m,k;int countb(int aim)
{int ret = 0;for (int i = 0; i < n; i++){if (aim & (1ll << i)){ret++;}}return ret;
}void solve()
{cin >> n >> m >> k;//n行m列  等价  n列m行//n列可统计状压vector<int>nums(1 << n);for (int i = 0; i < (1ll << n); i++){nums[i] = countb(i);}vector<vector<vector<vector<int>>>>dp(m+1, vector<vector<vector<int>>>(		1ll<<n, vector<vector<int>>(1ll << n,vector<int>(k+1)	)  )	 );//第几行 本行状态 前一行状态 个数 == 方案数//dp[0][0][0][0] = 1;//0行什么也不放。第一行肯定会摸一下,方案数是1//for (int h = 1; h <= m; h++){for (int i = 0; i < (1ll << n); i++)//本行{for (int j = 0; j < (1ll << n); j++)//前一行{for (int ii = 0; ii < (1ll << n); ii++)//前两行{for (int num = nums[i]; num <= k; num++){if ((i << 2 & j) || (i >> 2 & j))continue;if ((i << 1 & ii) || (i >> 1 & ii))continue;dp[h][i][j][num] = (dp[h][i][j][num] + dp[h - 1][j][ii][num - nums[i]])%mod;}}}}}//后面都是0也包括了只在前几行放的。。//动归int ans = 0;for (int i = 0; i < (1ll << n); i++)//本行{for (int j = 0; j < (1ll << n); j++)//前一行{ans = (ans + dp[m][i][j][k]) % mod;}}cout << ans;return;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;//cin >> t;for (int i = 1; i <= t; i++){solve();}return 0;
}
相关文章:
P8756 [蓝桥杯 2021 省 AB2] 国际象棋 状压dp统计情况数的一些小理解
目录 建议有状压基础再食用:本题的状态转移方程是 dp代码片:参考代码 建议有状压基础再食用: n行m列 等价 n列m行 ,因为n比较小,int是32位足够了,我们用比特位统计每一行的状态。 本题的状态转移方程是 dp[h][i][j]…...
春节放大招,阿里通义千问Qwen1.5开源发布
2月6日阿里发布了通义千问1.5版本,包含6个大小的模型,“Qwen” 指的是基础语言模型,而 “Qwen-Chat” 则指的是通过后训练技术如SFT(有监督微调)和RLHF(强化学习人类反馈)训练的聊天模型。 模型…...
grafana+prometheus+hiveserver2(jmx_exporter+metrics)
一、hiveserver2开启metrics,并启动jmx_exporter 1、修改hive-site.xml文件开启metrics <property><name>hive.server2.metrics.enabled</name><value>true</value> </property> <property><name>hive.service.m…...
Redis系列——Lua脚本和redis事务的应用
介绍 Lua脚本 背景 Redis是一种抽象数据类型的特定领域语言,由各种命令组成。大多数命令专门用于操作不通的数据类型。每次发送命令均需要执行至此网络请求。所以Redis提供了一个编程接口,支持服务器执行用户自定义的任意脚本。有助于减少网络流量&am…...
rtt设备驱动框架面向对象学习-i2c总线
本来想着i2c和spi是一样的,标题都想抄袭成《rtt设备驱动框架学习-i2c总线和设备》,然后看过源码发现,i2c没有分开总线和设备,我想着正常它和spi一样有总线和设备,设备存在竞争。估计是因为i2c设备可以通过i2c地址区分&…...
Golang 基础 Go Modules包管理
Golang 基础 Go Modules包管理 在 Go 项目开发中,依赖包管理是一个非常重要的内容,依赖包处理不好,就会导致编译失败,本文将系统介绍下 Go 的依赖包管理工具。 我会首先介绍下 Go 依赖包管理工具的历史,并详细介绍下…...
图数据库 之 Neo4j - 背景介绍(1)
引言 Neo4j是一种高性能的图数据库,它专门设计用于存储、管理和查询大规模的图数据。与传统的关系型数据库不同,Neo4j以图的形式存储数据,其中节点表示实体,边表示实体之间的关系。这种图数据模型非常适合表示复杂的关系和连接。…...
JAVA中的单例模式->饿汉式
一、步骤 1.构造器私有化>防止直接new // 步骤一、构造器私有化>防止直接new private GirlFriend(String name){System.out.println("构造器被调用");this.name name; } 2.类的内部创建对象 // 步骤二、类的内部创建对象(该对象是static&#x…...
从零开始手写mmo游戏从框架到爆炸(三)— 服务启动接口与网络事件监听器
导航:从零开始手写mmo游戏从框架到爆炸(零)—— 导航-CSDN博客 上一章我们完成了netty服务启动的相关抽象(https://blog.csdn.net/money9sun/article/details/136025471),这一章我们再新增一个全…...
git 合并多条提交记录
我要合并多条提交记录(合并前7条为一条),实现如下效果: 使用git rebase // 查看前10个commit git log -10 // 将7个commit压缩成一个commit;注意:vim编辑器 git rebase -i HEAD~4 // add已经跟踪的文件 g…...
C++多线程:this_thread 命名空间
std::this_thread 是 C 标准库中提供的一个命名空间,它包含了与当前线程相关的功能。这个命名空间提供了许多与线程操作相关的工具,使得在多线程环境中更容易进行编程。 源码类似于如下: namespace std{namespace this_thread{//...........…...
《山雨欲来-知道创宇 2023 年度 APT 威胁分析总结报告》
下载链接: https://pan.baidu.com/s/1eaIOyTk12d9mcuqDGzMYYQ?pwdzdcy 提取码: zdcy...
Qt信号和槽机制(什么是信号和槽,connect函数的形式,按钮的常用信号,QWidget的常用槽,自定义槽函数案例 点击按钮,输出文本)
一.什么是信号和槽 信号槽式Qt中的一个很重要的机制。信号槽实际上是观察者模式,当发生了感兴趣的事件,某一个操作就会被自动触发。当某个事件发生之后,比如按钮检测到自己被点击了一下,它就会发出一个信号。这种发出类似广播。如果有对象对…...
彻底弄懂mktemp命令的作用
mktemp 是一个在 Unix 和类 Unix 系统中用于创建临时文件或目录的命令行工具。它属于 GNU coreutils 套件的一部分。mktemp 的主要优点是它能够生成一个唯一的文件名,这有助于避免文件名冲突,并且可以安全地创建临时文件,因为这些文件通常只有…...
政安晨:示例演绎TensorFlow的官方指南(二){Estimator}
咱们接着演绎TensorFlow官方指南,我的这个系列的上一篇文章为: 政安晨:示例演绎TensorFlow的官方指南(一){基础知识}https://blog.csdn.net/snowdenkeke/article/details/136067030为什么要演绎官方指南,我…...
vue3:24—组件通信方式
目录 1、props 2、自定义事件 (emit) 3、mitt(任意组件的通讯) 4、v-model【封装ui组件库用的多,平时用的少。和vue2有点不同】 5、$attrs 6、$refs和$parent 7、provide和inject 8、pinia(即vue2中…...
WebGL+Three.js入门与实战——绘制水平移动的点、通过鼠标控制绘制(点击绘制、移动绘制、模拟画笔)
个人简介 👀个人主页: 前端杂货铺 🙋♂️学习方向: 主攻前端方向,正逐渐往全干发展 📃个人状态: 研发工程师,现效力于中国工业软件事业 🚀人生格言: 积跬步…...
大数据环境搭建(一)-Hive
1 hive介绍 由Facebook开源的,用于解决海量结构化日志的数据统计的项目 本质上是将HQL转化为MapReduce、Tez、Spark等程序 Hive表的数据是HDFS上的目录和文件 Hive元数据 metastore,包含Hive表的数据库、表名、列、分区、表类型、表所在目录等。 根据Hive部署模…...
mac电脑上使用android studio创建flutter项目
mac电脑环境配置可以看这篇文章:https://xiaoshen.blog.csdn.net/article/details/136068650 配置玩环境之后,开始创建第一个flutter项目:点击new flutter project或者new project都可以 然后选择flutter: 并将sdk配置为解压后的…...
Excel——分类汇总
1.一级分类汇总 Q:请根据各销售地区统计销售额总数。 第一步:排序,我们需要根据销售地区汇总数据,我们就要对【销售地区】的内容进行排序。点击【销售地区】列中任意一个单元格,选择【数据】——【排序】,…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
群晖NAS如何在虚拟机创建飞牛NAS
套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...
LangFlow技术架构分析
🔧 LangFlow 的可视化技术栈 前端节点编辑器 底层框架:基于 (一个现代化的 React 节点绘图库) 功能: 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...
