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:请根据各销售地区统计销售额总数。 第一步:排序,我们需要根据销售地区汇总数据,我们就要对【销售地区】的内容进行排序。点击【销售地区】列中任意一个单元格,选择【数据】——【排序】,…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
Python学习(8) ----- Python的类与对象
Python 中的类(Class)与对象(Object)是面向对象编程(OOP)的核心。我们可以通过“类是模板,对象是实例”来理解它们的关系。 🧱 一句话理解: 类就像“图纸”,对…...
李沐--动手学深度学习--GRU
1.GRU从零开始实现 #9.1.2GRU从零开始实现 import torch from torch import nn from d2l import torch as d2l#首先读取 8.5节中使用的时间机器数据集 batch_size,num_steps 32,35 train_iter,vocab d2l.load_data_time_machine(batch_size,num_steps) #初始化模型参数 def …...
Qt Quick Controls模块功能及架构
Qt Quick Controls是Qt Quick的一个附加模块,提供了一套用于构建完整用户界面的UI控件。在Qt 6.0中,这个模块经历了重大重构和改进。 一、主要功能和特点 1. 架构重构 完全重写了底层架构,与Qt Quick更紧密集成 移除了对Qt Widgets的依赖&…...
接口 RESTful 中的超媒体:REST 架构的灵魂驱动
在 RESTful 架构中,** 超媒体(Hypermedia)** 是一个核心概念,它体现了 REST 的 “表述性状态转移(Representational State Transfer)” 的本质,也是区分 “真 RESTful API” 与 “伪 RESTful AP…...
理想汽车5月交付40856辆,同比增长16.7%
6月1日,理想汽车官方宣布,5月交付新车40856辆,同比增长16.7%。截至2025年5月31日,理想汽车历史累计交付量为1301531辆。 官方表示,理想L系列智能焕新版在5月正式发布,全系产品力有显著的提升,每…...
【Vue】scoped+组件通信+props校验
【scoped作用及原理】 【作用】 默认写在组件中style的样式会全局生效, 因此很容易造成多个组件之间的样式冲突问题 故而可以给组件加上scoped 属性, 令样式只作用于当前组件的标签 作用:防止不同vue组件样式污染 【原理】 给组件加上scoped 属性后…...
LTR-381RGB-01RGB+环境光检测应用场景及客户类型主要有哪些?
RGB环境光检测 功能,在应用场景及客户类型: 1. 可应用的儿童玩具类型 (1) 智能互动玩具 功能:通过检测环境光或物体颜色触发互动(如颜色识别积木、光感音乐盒)。 客户参考: LEGO(乐高&#x…...
视觉slam--框架
视觉里程计的框架 传感器 VO--front end VO的缺点 后端--back end 后端对什么数据进行优化 利用什么数据进行优化的 后端是怎么进行优化的 回环检测 建图 建图是指构建地图的过程。 构建的地图是点云地图还是什么信息的地图? 建图并没有一个固定的形式和算法…...
