灌溉机器人 状压dp

灌溉机器人

题目描述

农田灌溉是一项十分费体力的农活,特别是大型的农田。小明想为农民伯伯们减轻农作负担,最近在研究一款高科技——灌溉机器人。它可以在远程电脑控制下,给农田里的作物进行灌溉。

现在有一片 N 行 M 列的农田。农田的土壤有两种类型:类型 H 和类型 P,每一个格子上的土壤类型相同。其中类型 P 的土壤硬度较大,可以用来布置灌溉机器人,但是一个格子上只能布置一台。类型 H 的土壤不能布置灌溉机器人。一台灌溉机器人的灌溉区域如下图所示:

image.png
黄色表示灌溉机器人布置的格子,红色表示其灌溉区域,即四个方向上各外扩展两个格子。

小明想在农田上尽可能多布置一些灌溉机器人,但是任意一台机器人不能在任意一台机器人的灌溉区域里,否则机器容易进水出故障。现在已知农田每个格子的土壤类型,请你来帮小明计算一下,小明最多能布置多少台灌溉机器人。

输入描述

输入第一行输入两个正整数N,M(N≤100,M≤10),表示农田的行和列。

接下来输入 N 行,每行输入连续的 M 个字符(P或者H),中间没有空格。表示农田每个格子上的土壤类型。

输出描述

输出一行,输出一个整数,表示最多能摆放的灌溉机器人的数量。

用例输入 1

3 4
PHPP
PHPP
PHHP

用例输出 1

3

代码

#include <bits/stdc++.h>
using namespace std;
#define max_Heap(x) priority_queue<x, vector<x>, less<x>>
#define min_Heap(x) priority_queue<x, vector<x>, greater<x>>
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
const double PI = acos(-1);int n, m;              // n行m列
char field[106][16];   // 记录土壤是否能布置灌溉机器人
vector<int> s[106];    // 存储第i行中所有的合法状态
int dp[106][106][106]; // dp表示遍历到第i行时,第i行状态为序号j,第i-1行状态为序号k时最大能摆放的机器人数量int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);unordered_map<int, int> mp;cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 0; j < m; j++){cin >> field[i][j]; // 读入土壤类型}}// 预处理存储第i行中所有的合法状态for (int i = 1; i <= n; i++){for (int j = 0; j < (1 << m); j++){bool ok = 1; // 是否合法for (int k = 0; k < m; k++){if (((j >> k) & 1) && (field[i][k] == 'H')) // 如果在H类型土壤上放机器人,则不合法{ok = 0;break;}}if ((j & (j << 1)) || (j & (j << 2)) || (j & (j >> 1)) || (j & (j >> 2))) // 判断左右方向扩展的两个格子是否合法{ok = 0;}if (ok)s[i].push_back(j);}}// 预处理每一行中各种放置状态机器人的个数,并存储在map中for (int i = 0; i < (1 << m); i++){int cnt = 0;for (int j = 0; j < m; j++){if ((i >> j) & 1)cnt++;}mp[i] = cnt;}// 初始化第一行的dpfor (int i = 0; i < s[1].size(); i++){dp[1][i][0] = mp[s[1][i]];}s[0].push_back(0);// 枚举到第i行for (int i = 1; i <= n; i++){// 枚举当前行所有状态for (int num3 = 0; num3 < s[i].size(); num3++){int s3 = s[i][num3];// 枚举上一行所有状态for (int num2 = 0; num2 < s[i - 1].size(); num2++){int s2 = s[i - 1][num2];// 枚举上上一行所有状态for (int num1 = 0; num1 < s[i - 2].size(); num1++){int s1 = s[i - 2][num1];// 如果三行之间的关系合法,则更新dpif (!(s1 & s2) && !(s1 & s3) && !(s2 & s3))dp[i][num3][num2] = max(dp[i][num3][num2], dp[i - 1][num2][num1] + mp[s3]);}}}}int ans = 0;// 遍历找最大值for (int i = 0; i < s[n].size(); i++){for (int j = 0; j < s[n - 1].size(); j++){ans = max(ans, dp[n][i][j]);}}cout << ans;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/320439.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

[Java EE] 多线程(八):CAS问题与JUC包

&#x1f338;个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 &#x1f3f5;️热门专栏:&#x1f355; Collection与数据结构 (90平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm1001.2014.3001.5482 &#x1f9c0;Java …

8个细节决定你的活动策划推广成败-华媒舍

活动策划和推广对于一个成功的活动来说至关重要。许多因素会影响活动的成功与否&#xff0c;以下我将介绍8个关键细节&#xff0c;这些细节能够决定活动的策划与推广的成败。 1. 目标定位 活动策划必须明确目标。你需要确定你的活动是为了推广何种产品或服务&#xff0c;吸引什…

简述前后端分离架构案例

Hello , 这里是小恒不会java 。今晚1点写写关于RESTful接口的使用案例&#xff0c;本文会通过django原生js前后端分离的案例简单讲解。本文带你认识一下简化版的前后端分离架构 代码 本文案例代码在GitHub上 https://github.com/lmliheng/fontend前后端分离 先说说什么是前后…

rust将json字符串直接转为map对象或者hashmap对象

有些时候我们还真的不清楚返回的json数据里面到底有哪些数据&#xff0c;数据类型是什么等&#xff0c;这个时候就可以使用批处理的方式将json字符串转为一个对象&#xff0c;然后通过这个对象的get方法来获取json里面的数据。 pub async fn test_json(&self) {let json_st…

『项目整理』易CAR通项目说明文档-我的第一款APP

『项目整理』易CAR通项目说明文档-我的第一款APP 项目介绍功能介绍技术栈介绍实现效果如何运行备注 项目介绍 易CAR通项目是我的第一个Android项目。是一款结合了AR技术的模仿懂车帝的看车软件。因为是初学&#xff0c;所示实现的效果差强人意&#xff0c;很多的功能界面只实现…

【论文阅读】Learning Texture Transformer Network for Image Super-Resolution

Learning Texture Transformer Network for Image Super-Resolution 论文地址Abstract1. 简介2.相关工作2.1单图像超分辨率2.2 Reference-based Image Super-Resolution 3. 方法3.1. Texture TransformerLearnable Texture Extractor 可学习的纹理提取器。Relevance Embedding.…

nginxconfig.io项目nginx可视化配置--搭建-视频

项目地址 https://github.com/digitalocean/nginxconfig.io搭建视频 nginxconfig.io搭建 nginxconfig.io搭建 展示效果 找到这个项目需要的docker镜像&#xff0c;有项目需要的node的版本 docker pull node:20-alpine运行这个node容器,在主机中挂载一个文件夹到容器中 主机&a…

MATLAB 变换

MATLAB 变换&#xff08;Transforms&#xff09; MATLAB提供了用于处理诸如Laplace和Fourier变换之类的变换的命令。转换在科学和工程中用作简化分析和从另一个角度查看数据的工具。 例如&#xff0c;傅立叶变换允许我们将表示为时间函数的信号转换为频率函数。拉普拉斯变换使…

微搭低代码入门03页面管理

目录 1 创建页面2 页面布局3 页面跳转总结 上一篇我们介绍了应用的基本操作&#xff0c;掌握了应用的概念后接着我们需要掌握页面的常见操作。 1 创建页面 打开应用的编辑器&#xff0c;在顶部导航条点击创建页面图标 在创建页面的时候可以从空白新建&#xff0c;也可以使用模…

screen

sLinux&#xff1a;screen命令——命令行的窗口操作_screen命令关闭窗口-CSDN博客文章浏览阅读4.2k次。功能&#xff1a;管理命令行终端切换的软件&#xff0c;常用于远程连接Linux过程中&#xff0c;同时使用多个命令行窗口。在窗口运行中的程序&#xff0c;记住窗口名字前面的…

nodejs实战——搭建websocket服务器

本博客主要介绍websocket服务器库安装&#xff0c;并举了一个简单服务器例子。 服务器端使用websocket需要安装nodejs websocket。 cd 工程目录 # 此刻我们需要执行命令&#xff1a; sudo npm init上述命令创建package.json文件&#xff0c;系统会提示相关配置。 我们也可以使…

一款开源的原神工具箱,专为现代化 Windows 平台设计,旨在改善桌面端玩家的游戏体验

Snap.Hutao 胡桃工具箱是一款以 MIT 协议开源的原神工具箱&#xff0c;专为现代化 Windows 平台设计&#xff0c;旨在改善桌面端玩家的游戏体验。通过将既有的官方资源与开发团队设计的全新功能相结合&#xff0c;提供了一套完整且实用的工具集&#xff0c;且无需依赖任何移动设…

im即时通讯源码/仿微信app源码+php即时通讯源码带红包+客服+禁言等系统php+uniapp开发

即时通讯(IM)系统是现代互联网应用中不可或缺的一部分&#xff0c;它允许用户进行实时的文本、语音、视频交流。随着技术的发展&#xff0c;IM系统的功能越来越丰富&#xff0c;如红包、客服、禁言等。本文将探讨如何使用PHP语言开发一个功能完备的即时通讯系统&#xff0c;包括…

如何让 PDF 书签从杂乱无序整洁到明丽清新

1、拉取书签&#xff08;详细步骤看文末扩展阅读&#xff09; 原状态 —— 杂乱无序 自动整理后的状态 —— 错落有致&#xff0c;但摩肩接踵 2、开始整理 全选自动整理后的书签&#xff0c;剪切 访问中英混排排版优化 - 油条工具箱 https://utils.fun/cn-en 1 粘贴 → 2 …

Linux下安装snaphu

1、官网下载安装包 2、解压&#xff0c;移动文件夹到/usr/local/下 3、在/usr/local/下创建man&#xff0c;在man下创建man1文件夹 4、进入到snaphu的src文件夹里&#xff0c;执行sudo make&#xff0c;如果报错 在这个 Makefile 中&#xff0c;-arch x86_64 是 macOS 特定的…

最近惊爆谷歌裁员

Python团队还没解散完&#xff0c;谷歌又对Flutter、Dart动手了。 什么原因呢&#xff0c;猜测啊。 谷歌裁员Python的具体原因可能是因为公司在进行技术栈的调整和优化。Python作为一种脚本语言&#xff0c;在某些情况下可能无法提供足够的性能或者扩展性&#xff0c;尤其是在…

[Unity常见小问题]打包ios后无法修改模型透明度

问题 在Editor下可以使用如下代码去修改模型的材质的透明度&#xff0c;但是打包ios后无法对透明度进行修改且没有任何warning和error using System.Collections; using System.Collections.Generic; using UnityEngine;public class NewBehaviourScript : MonoBehaviour {[R…

2010-2022年上市公司彭博ESG披露评分、分项得分数据

2010-2022年上市公司彭博ESG披露评分、分项得分数据 1、时间&#xff1a;2010-2022年 2、来源&#xff1a;Bloomberg ESG 指数 3、指标&#xff1a;股票代码、股票简称、年份、ESG披露评分、环境披露评分、社会信息披露评分、治理披露评分 4、范围&#xff1a;上市公司 5、…

RocketMQ SpringBoot 3.0不兼容解决方案

很多小伙伴在项目升级到springBoot3.0版本以上之后&#xff0c;整合很多中间件会有很多问题&#xff0c;下面带小伙伴解决springBoot3.0版本以上对于RocketMQ 不兼容问题 报错信息 *************************** APPLICATION FAILED TO START *************************** Des…

基于alpha shapes的边缘点提取(matlab)

1、原理介绍 由Edelsbrunner H提出的alpha shapes算法是一种简单、有效的快速提取边界点算法。其克服了点云边界点形状影响的缺点&#xff0c;可快速准确提取边界点。如下图所示&#xff0c;对于任意形状的平面点云&#xff0c;若一个半径为a的圆&#xff0c;绕其进行滚动&…