灌溉机器人 状压dp

灌溉机器人

题目描述

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

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

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

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

输入描述

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

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

输出描述

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

用例输入 1

3 4
PHPP
PHPP
PHHP
1
2
3
4

用例输出 1

3
1

代码

#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;
    }

    // 初始化第一行的dp
    for (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];
                    // 如果三行之间的关系合法，则更新dp
                    if (!(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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111