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

news/2025/2/15 5:29:24/

注意事项:
本题为"状态压缩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 使用选…