C++---状态压缩dp---炮兵阵地(每日一道算法2023.4.17)

news/2024/5/19 22:40:18/

注意事项:
本题为"状态压缩dp—蒙德里安的梦想"和"状态压缩dp—小国王"和"状态压缩dp—玉米田"的近似题,建议先阅读这三篇文章并理解。

题目:
司令部的将军们打算在 N×M 的网格地图上部署他们的炮兵部队。
一个 N×M 的地图由 N 行 M 列组成,地图的每一格可能是山地(用 H 表示),也可能是平原(用 P 表示),如下图。

在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示:
请添加图片描述
如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻击到的区域:沿横向左右各两格,沿纵向上下各两格。
图上其它白色网格均攻击不到。
从图上可见炮兵的攻击范围不受地形的影响。

现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵部队之间不能互相攻击,即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内),在整个地图区域内最多能够摆放多少我军的炮兵部队。

输入格式
第一行包含两个由空格分割开的正整数,分别表示 N 和 M;
接下来的 N 行,每一行含有连续的 M 个字符(P 或者 H),中间没有空格。按顺序表示地图中每一行的数据。

输出格式
仅一行,包含一个整数 K,表示最多能摆放的炮兵部队的数量。

数据范围
N≤100,M≤10

输入:
5 4
PHPP
PPHH
PPPP
PHPP
PHHP
输出:
6

#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;const int N = 110, M = 1 << 10;
int n, m, cnt[M], st[N], f[2][M][M];
char t;
vector<int> state, state_trans[M];bool check(int s) {     //判断同一行中,三格内只能同时存在一个1,也就是炮兵不能互相攻击到为合法状态,for (int i = 0; i<m; i++) {if ((s >> i & 1) && ((s >> (i+1) & 1) | (s >> (i+2) & 1))) return false;}return true;
}
int count(int s) {      //计算当前状态中1的数量int res = 0;for (int i = 0; i<m; i++) res += (s >> i & 1);return res;
}int main() {cin >> n >> m;//预处理所有读入,将每一行的地势转换为二进制,1为山地,0为平原for (int i = 1; i<=n; i++) {for (int j = 0; j<m; j++) {cin >> t;st[i] += ((t=='H') << j);}}//预处理所有合法状态for (int i = 0; i < (1 << m); i++) {if (check(i)) {state.push_back(i);cnt[i] = count(i);}}//预处理所有合法状态转移, 本题行与行之间的限制就是不能在同一列摆放炮兵for (auto &a : state) {for (auto &b : state) {if ((a&b)==0) state_trans[a].push_back(b);}}//dpfor (int i = 1; i<=n+2; i++) {          //枚举地图的每一行,for (auto &a : state) {       //枚举所有合法状态a(第i层)if ((a & st[i])==0) {           //当状态a没有在山地上部署的炮兵,那就可以进行状态转移,=for (auto &b : state_trans[a]) {        //枚举所有能从a转移到的状态b,(第i-1层)for (auto &c : state_trans[b]) {    //枚举所有能从b转移到的状态c,(第i-2层)if ((a&c)==0) {             //a能转移到b,b能转移到c,但不代表a能转移到c(比如a=010,b=001,c=110,a-b合法,b-c合法,a-c不合法)f[i&1][a][b] = max(f[i&1][a][b], f[(i-1)&1][b][c] + cnt[a]);}}}}}}//这里还是和之前的状压dp一样,n+2是小优化,表示:前n+2行已经摆完,且第n+2行状态为0(一个炮兵不摆),第n+1行状态为0,//那么就和sum(f[n][1~m][1~m])的方案数是一样的。cout << f[(n+2)&1][0][0];return 0;
}

思路:
和"小国王"以及"玉米田"那两题非常相似,强烈建议先理解那两道题。

还是经典的y式dp法:
1.状态表示
f[i][j][k]:
i行的炮兵已经摆好(包括第i行),且第i行的状态为j,第i-1行状态为k的所有方案。
属性为Max(摆放最多的炮兵),
(状态为 j/k 指的是二进制来表示炮兵摆放的状况,状压dp的常用手段),

2.状态计算
经过前几道状压dp的洗礼,还是先来分别分析一下"状态"和"转移":
1.什么情况下状态a(第i行)是合法的?
一,单行内炮兵不能互相攻击到(三格内至多只能存在一个炮兵)。
二,炮兵不能摆放在山地上。

2.什么情况下状态a转移到状态b(第i行和第i-1行)是合法的?
一,a和b不能在同一列同时有炮兵存在。

最后符合上述条件,就可以状态转移啦,
f[i][a][b] = max(f[i][a][b], f[i-1][b][c] + cnt[a])
从实际意义出发:
1.f[i][a][b] = 前i行已经摆完,且第i行状态为a,第i-1行状态为b,
2.f[i-1][b][c] = 前i-1行已经摆完,且第i-1行状态为b,第i-2行状态为c,
那么用2更新1,就需要加上当前状态a中炮兵的摆放数量即可。

如果有所帮助请给个免费的赞吧~有人看才是支撑我写下去的动力!

声明:
算法思路来源为y总,详细请见https://www.acwing.com/
本文仅用作学习记录和交流


http://www.ppmy.cn/news/48103.html

相关文章

计算机组成原理(考研408)练习题#1

用于复习408或计算机组成原理期末考试。如有错误请在评论区指出。 So lets start studying with questions! それでは、問題の勉強を始めましょう&#xff01; 1. 设有一个 1MB 容量的存储器&#xff0c;字长为 32 位&#xff0c;问&#xff1a; &#xff08;1&#xff09;按…

【数据结构】第十三站:排序(上)

本文目录 一、排序概念二、插入排序1.插入排序的基本思想2.算法实现3.时间复杂度分析 三、希尔排序1. 希尔排序的思想2.希尔排序的代码实现3.希尔排序和插入排序的性能测试比较4.希尔排序的时间复杂度 四、直接选择排序1.基本思想2.直接选择排序的步骤3.直接选择排序的代码实现…

【C++】vector的使用

文章目录 1. 主要结构2. 构造函数与复制重载3. 迭代器4. 容量相关1.容量读取2.容量修改 5. 数据访问6. 数据修改1. 尾插尾删2.任意位置的插入删除 7.其他接口 在之前我们学习了string的使用与模拟实现&#xff0c;在参考文档中可以发现&#xff0c;vector和string以及其他的容器…

ElasticJob

官网 :: ElasticJob ElasticJob 是面向互联网生态和海量任务的分布式调度解决方案&#xff0c;由两个相互独立的子项目 ElasticJob-Lite 和 ElasticJob-Cloud 组成。 它通过弹性调度、资源管控、以及作业治理的功能&#xff0c;打造一个适用于互联网场景的分布式调度解决方案&…

​破除“内卷”,什么才是高阶智能座舱更优方案?

下一代智能座舱雏形已现。 从多屏互动到舱内全场景交互&#xff0c;从中控娱乐快速延伸到更多元化的车内娱乐平台&#xff1b;越来越多元化功能集中上车&#xff0c;座舱空间的营造&#xff08;包括氛围灯、香氛等&#xff09;以及AR技术的应用等等&#xff0c;开始深刻影响着…

[渗透测试笔记] 56.日薪2k的蓝队hw中级定级必备笔记系列篇4之面试必备web中间件漏洞汇总

文章目录 1.Weblogic1.1 任意文件上传漏洞(CVE-2018-2894)1.2 XML远程代码执行RCE漏洞(CVE-2020-14882)1.3 SSRF漏洞(CVE-2014-4210)1.4 Java反序列化漏洞(CVE-2018-2628)2.Nginx2.1 解析漏洞2.2 Nginx文件名逻辑漏洞(CVE-2013-4547)2.3 Nginx越界读取缓存漏洞(CVE-2017-752…

代码随想录刷题笔记2

文章目录 二叉树递归遍历统一迭代形式层序遍历迭代形式——队列 题型删除普通二叉树目标节点两棵树比较 递归模板深度、高度问题完全二叉树判断完全二叉树 平衡二叉树左叶子最大树二叉搜索树最近公共祖先 二叉树 递归遍历 递归三部曲 确定递归函数的 参数 与 返回值。确定终止…

【Vue全家桶】Pinia状态管理

【Vue全家桶】Pinia状态管理 文章目录 【Vue全家桶】Pinia状态管理写在前面一、认识Pinia1.1 认识Pinia1.2 为什么使用Pinia&#xff1f; 二、 Store2.1 定义Store2.2 Option对象2.3 setup函数2.4 使用定义的Store 三、Pinia核心概念State3.1 定义State3.2 操作State3.3 使用选…

为何MySQL 8.0开始取消了查询缓存

官方文档说明&#xff1a;MySQL :: MySQL 8.0: Retiring Support for the Query Cache MySQL查询缓存是查询结果缓存。它将以SEL开头的查询与哈希表进行比较&#xff0c;如果匹配&#xff0c;则返回上一次查询的结果。 进行匹配时&#xff0c;查询必须逐字节匹配&#xff0c;例…

Android:usb转232串口通信

准备工作 首先得adb进入盒子root模式&#xff0c;将/dev/ttys1这个文件改为777&#xff0c;使得所有用户可操作 adb root adb remount adb shell 进入设备的root模式&#xff0c;执行 chmod 777 /dev/ttys1 执行完成后退出 exit 再执行 adb shell chmod 666 /dev/ttyS1 如…

比较运算符、关键字子查询MySQL数据库 (头歌实践教学平台)

文章目的初衷是希望学习笔记分享给更多的伙伴&#xff0c;并无盈利目的&#xff0c;尊重版权&#xff0c;如有侵犯&#xff0c;请官方工作人员联系博主谢谢。 目录 第1关&#xff1a;带比较运算符的子查询 任务描述 相关知识 子查询 带比较运算符的子查询 编程要求 第2关…

第二章 法的内容与形式

目录 第一节 法的内容与形式的概念 一、法的内容与形式的含义 二、法的内容和形式的关系 第二节 法律权利与法律义务 一、权利和义务的概念 二、权利和义务的分类 三、权利与义务的联系 第三节 法的成文形式与不成文形式 一、历史上各种法的表现形式 二、成文法与不成文…

Vue中组件传值

Vue官网链接-向子组件传递数据 Vue官网-Prop 父组件将值传递给子组件 父组件中的值可以通过v-bind与子组件中的props属性将值传递给子组件&#xff0c;也可以通过v-on与this.$emit()间接被子组件中的函数调用 1、使用v-bind将父组件中data中的键与子组件中的props键进行绑定 …

【SpringBoot】一:SpringBoot的基础(下)

文章目录 1.外部化的配置1.1 配置文件基础1.1.1 配置文件格式1.1.2 application文件1.1.3 application.properties1.1.4 application.yml1.1.5 environment1.1.6 组织多文件1.1.7多环境配置 1.2 绑定Bean1.2.1 简单的属性绑定1.2.2 嵌套Bean1.2.3 扫描注解1.2.4 处理第三方库对…

Vue中mixins(混入)的介绍和使用

什么是Mixin&#xff1f; 想要使用一个事物或者工具&#xff0c;我们首要先了解它是什么&#xff0c;这样我们才好对症下药。 其实Mixin不是Vue专属的&#xff0c;可以说它是一种思想&#xff0c;也可以说它就是混入的意思&#xff0c;在很多开发框架中都实现了Mixin(混入)&a…

异常(throwable)

异常 异常分类 &#xff08;1&#xff09;Throwable类 所有的异常类型都是它的子类&#xff0c;它派生两个子类Error、Exception。 &#xff08;2&#xff09;Error类 表示仅靠程序本身无法恢复的严重错误&#xff08;内存溢出动态链接失败、虚拟机错误&#xff09;&#…

Seata强一致性事务模式XA的设计理念

承接上文分布式事务Seata-AT模式 XA规范是什么? 是分布式事务处理DTP&#xff08;Distributed Transaction Processing&#xff09;的标准。是描述全局的事务管理器和局部的资源管理器之间的接口规范。允许多个资源&#xff08;如数据库、应用服务、消息队列&#xff09;在同…

class与typename的异同

一、class与typename的相同点 typename关键字常用于函数模板&#xff0c;这里首先引入函数模板的概念&#xff1a;函数模板代表了一个函数家族&#xff0c;该函数模板与类型无关&#xff0c;在使用时被参数化&#xff0c;根据实参类型产生函数的特定 类型版本 //函数模板格式…

idea 配置docker 进行上传镜像,部署启动容器

前言 在我们开发测试过程中&#xff0c;需要频繁的更新docker镜像&#xff0c;然而默认情况下&#xff0c;docker的2375端口是关闭的&#xff0c;下面介绍如何打开端口。 修改docker配置文件 操作步骤&#xff1a; 1.1、修改配置 登录docker所在服务器&#xff0c;修改docker…

深入浅出剖析JAVA多线程原理

1. 线程基础知识 1.1 线程与进程 1.1.1 进程 ●程序由指令和数据组成&#xff0c;但这些指令要运行&#xff0c;数据要读写&#xff0c;就必须将指令加载至 CPU&#xff0c;数据加载至内存。在指令运行过程中还需要用到磁盘、网络等设备。进程就是用来加载指令、管理内存、管理…