做外贸的国际网站有哪些,设计灵感,企业名录搜索软件下载,企业类网页设计灌溉机器人
题目描述
农田灌溉是一项十分费体力的农活#xff0c;特别是大型的农田。小明想为农民伯伯们减轻农作负担#xff0c;最近在研究一款高科技——灌溉机器人。它可以在远程电脑控制下#xff0c;给农田里的作物进行灌溉。
现在有一片 N 行 M 列的农田。农田的土…灌溉机器人
题目描述
农田灌溉是一项十分费体力的农活特别是大型的农田。小明想为农民伯伯们减轻农作负担最近在研究一款高科技——灌溉机器人。它可以在远程电脑控制下给农田里的作物进行灌溉。
现在有一片 N 行 M 列的农田。农田的土壤有两种类型类型 H 和类型 P每一个格子上的土壤类型相同。其中类型 P 的土壤硬度较大可以用来布置灌溉机器人但是一个格子上只能布置一台。类型 H 的土壤不能布置灌溉机器人。一台灌溉机器人的灌溉区域如下图所示 黄色表示灌溉机器人布置的格子红色表示其灌溉区域即四个方向上各外扩展两个格子。
小明想在农田上尽可能多布置一些灌溉机器人但是任意一台机器人不能在任意一台机器人的灌溉区域里否则机器容易进水出故障。现在已知农田每个格子的土壤类型请你来帮小明计算一下小明最多能布置多少台灌溉机器人。
输入描述
输入第一行输入两个正整数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_queuex, vectorx, lessx
#define min_Heap(x) priority_queuex, vectorx, greaterx
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
typedef pairlong long, long long PLL;
const double PI acos(-1);int n, m; // n行m列
char field[106][16]; // 记录土壤是否能布置灌溉机器人
vectorint 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_mapint, 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;
}
