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

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统计情况数的一些小理解

目录 建议有状压基础再食用&#xff1a;本题的状态转移方程是 dp代码片:参考代码 建议有状压基础再食用&#xff1a; n行m列 等价 n列m行 &#xff0c;因为n比较小&#xff0c;int是32位足够了&#xff0c;我们用比特位统计每一行的状态。 本题的状态转移方程是 dp[h][i][j]…...

春节放大招,阿里通义千问Qwen1.5开源发布

2月6日阿里发布了通义千问1.5版本&#xff0c;包含6个大小的模型&#xff0c;“Qwen” 指的是基础语言模型&#xff0c;而 “Qwen-Chat” 则指的是通过后训练技术如SFT&#xff08;有监督微调&#xff09;和RLHF&#xff08;强化学习人类反馈&#xff09;训练的聊天模型。 模型…...

grafana+prometheus+hiveserver2(jmx_exporter+metrics)

一、hiveserver2开启metrics&#xff0c;并启动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是一种抽象数据类型的特定领域语言&#xff0c;由各种命令组成。大多数命令专门用于操作不通的数据类型。每次发送命令均需要执行至此网络请求。所以Redis提供了一个编程接口&#xff0c;支持服务器执行用户自定义的任意脚本。有助于减少网络流量&am…...

rtt设备驱动框架面向对象学习-i2c总线

本来想着i2c和spi是一样的&#xff0c;标题都想抄袭成《rtt设备驱动框架学习-i2c总线和设备》&#xff0c;然后看过源码发现&#xff0c;i2c没有分开总线和设备&#xff0c;我想着正常它和spi一样有总线和设备&#xff0c;设备存在竞争。估计是因为i2c设备可以通过i2c地址区分&…...

Golang 基础 Go Modules包管理

Golang 基础 Go Modules包管理 在 Go 项目开发中&#xff0c;依赖包管理是一个非常重要的内容&#xff0c;依赖包处理不好&#xff0c;就会导致编译失败&#xff0c;本文将系统介绍下 Go 的依赖包管理工具。 我会首先介绍下 Go 依赖包管理工具的历史&#xff0c;并详细介绍下…...

图数据库 之 Neo4j - 背景介绍(1)

引言 Neo4j是一种高性能的图数据库&#xff0c;它专门设计用于存储、管理和查询大规模的图数据。与传统的关系型数据库不同&#xff0c;Neo4j以图的形式存储数据&#xff0c;其中节点表示实体&#xff0c;边表示实体之间的关系。这种图数据模型非常适合表示复杂的关系和连接。…...

JAVA中的单例模式->饿汉式

一、步骤 1.构造器私有化>防止直接new // 步骤一、构造器私有化>防止直接new private GirlFriend(String name){System.out.println("构造器被调用");this.name name; } 2.类的内部创建对象 // 步骤二、类的内部创建对象&#xff08;该对象是static&#x…...

从零开始手写mmo游戏从框架到爆炸(三)— 服务启动接口与网络事件监听器

导航&#xff1a;从零开始手写mmo游戏从框架到爆炸&#xff08;零&#xff09;—— 导航-CSDN博客 上一章我们完成了netty服务启动的相关抽象&#xff08;https://blog.csdn.net/money9sun/article/details/136025471&#xff09;&#xff0c;这一章我们再新增一个全…...

git 合并多条提交记录

我要合并多条提交记录&#xff08;合并前7条为一条&#xff09;&#xff0c;实现如下效果&#xff1a; 使用git rebase // 查看前10个commit git log -10 // 将7个commit压缩成一个commit&#xff1b;注意&#xff1a;vim编辑器 git rebase -i HEAD~4 // add已经跟踪的文件 g…...

C++多线程:this_thread 命名空间

std::this_thread 是 C 标准库中提供的一个命名空间&#xff0c;它包含了与当前线程相关的功能。这个命名空间提供了许多与线程操作相关的工具&#xff0c;使得在多线程环境中更容易进行编程。 源码类似于如下&#xff1a; namespace std{namespace this_thread{//...........…...

《山雨欲来-知道创宇 2023 年度 APT 威胁分析总结报告》

下载链接: https://pan.baidu.com/s/1eaIOyTk12d9mcuqDGzMYYQ?pwdzdcy 提取码: zdcy...

Qt信号和槽机制(什么是信号和槽,connect函数的形式,按钮的常用信号,QWidget的常用槽,自定义槽函数案例 点击按钮,输出文本)

一.什么是信号和槽 信号槽式Qt中的一个很重要的机制。信号槽实际上是观察者模式,当发生了感兴趣的事件&#xff0c;某一个操作就会被自动触发。当某个事件发生之后&#xff0c;比如按钮检测到自己被点击了一下&#xff0c;它就会发出一个信号。这种发出类似广播。如果有对象对…...

彻底弄懂mktemp命令的作用

mktemp 是一个在 Unix 和类 Unix 系统中用于创建临时文件或目录的命令行工具。它属于 GNU coreutils 套件的一部分。mktemp 的主要优点是它能够生成一个唯一的文件名&#xff0c;这有助于避免文件名冲突&#xff0c;并且可以安全地创建临时文件&#xff0c;因为这些文件通常只有…...

政安晨:示例演绎TensorFlow的官方指南(二){Estimator}

咱们接着演绎TensorFlow官方指南&#xff0c;我的这个系列的上一篇文章为&#xff1a; 政安晨&#xff1a;示例演绎TensorFlow的官方指南&#xff08;一&#xff09;{基础知识}https://blog.csdn.net/snowdenkeke/article/details/136067030为什么要演绎官方指南&#xff0c;我…...

vue3:24—组件通信方式

目录 1、props 2、自定义事件 &#xff08;emit&#xff09; 3、mitt&#xff08;任意组件的通讯&#xff09; 4、v-model【封装ui组件库用的多&#xff0c;平时用的少。和vue2有点不同】 5、$attrs 6、$refs和$parent 7、provide和inject 8、pinia&#xff08;即vue2中…...

WebGL+Three.js入门与实战——绘制水平移动的点、通过鼠标控制绘制(点击绘制、移动绘制、模拟画笔)

个人简介 &#x1f440;个人主页&#xff1a; 前端杂货铺 &#x1f64b;‍♂️学习方向&#xff1a; 主攻前端方向&#xff0c;正逐渐往全干发展 &#x1f4c3;个人状态&#xff1a; 研发工程师&#xff0c;现效力于中国工业软件事业 &#x1f680;人生格言&#xff1a; 积跬步…...

大数据环境搭建(一)-Hive

1 hive介绍 由Facebook开源的,用于解决海量结构化日志的数据统计的项目 本质上是将HQL转化为MapReduce、Tez、Spark等程序 Hive表的数据是HDFS上的目录和文件 Hive元数据 metastore&#xff0c;包含Hive表的数据库、表名、列、分区、表类型、表所在目录等。 根据Hive部署模…...

mac电脑上使用android studio创建flutter项目

mac电脑环境配置可以看这篇文章&#xff1a;https://xiaoshen.blog.csdn.net/article/details/136068650 配置玩环境之后&#xff0c;开始创建第一个flutter项目&#xff1a;点击new flutter project或者new project都可以 然后选择flutter&#xff1a; 并将sdk配置为解压后的…...

Excel——分类汇总

1.一级分类汇总 Q&#xff1a;请根据各销售地区统计销售额总数。 第一步&#xff1a;排序&#xff0c;我们需要根据销售地区汇总数据&#xff0c;我们就要对【销售地区】的内容进行排序。点击【销售地区】列中任意一个单元格&#xff0c;选择【数据】——【排序】&#xff0c…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...