题目#

[NOI2001] 炮兵阵地#

司令部的将军们打算在 $N\times M$ 的网格地图上部署他们的炮兵部队。

一个 $N\times M$ 的地图由 $N$ 行 $M$ 列组成，地图的每一格可能是山地（用 $\texttt{H}$ 表示），也可能是平原（用 $\texttt{P}$ 表示），如下图。

在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。

图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。

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

对于 $100\%$ 的数据， $N\le 100$ ， $M\le 10$ ，保证字符仅包含 P 与 H。

题解#

首先看到数据范围，直接状态压缩dp

考虑设计状态

先尝试f[i][j]表示推到第i行，且第i行的状态的二进制为j的，能放下的最多的炮兵部队

尝试转移

f[i][j]要从f[i-1][~]转移过来，但f[i-1][~]的状态包含的集合又不是都能用，所以没法转移

考虑加状态

f[i][j][fl]表示推到第i行，且第i行的状态的二进制为j的，第i-1行的状态为fl的，能放下的最多的炮兵部队

可以转移了

实现#

判断是否能放，二进制和地图与一下，二进制本身分别和其左移一位、两位与一下

其余同理

出现问题#

1.状压dp最好下标从0开始

2.学习了滚动数组

代码#

1
#include<bits/stdc++.h>
2

3
using namespace std;
4

5
int read()
6
{
7
  int f = 1, x = 0;
8
  char ch = getchar();
9
  while(ch < '0' || ch > '9')
10
  {
11
    if(ch == '-') f = -1;
12
    ch = getchar();
13
  }
14

15
  while(ch >= '0' && ch <= '9')
16
  {
17
    x = x * 10 + ch - '0';
18
    ch = getchar();
19
  }
20
  return f * x;
21
}
22

23
int n, m;
24

25
int Map[110];//如果是1表示山地，0表示平原
26

27
int f[3][1 << 10][1 << 10]; // i，当前状态，上一行状态
28
int num_of_1[1 << 10];
29

30

31
int getsum(int x)
32
{
33
  int ans = 0;
34
  while(x)
35
  {
36
    x &= (x - 1);
37
    ans++;
38
  }
39
  return ans;
40
}
41

42
int main()
43
{
44

45
  for(int i = 0;i < (1 << 10);i++)
46
  {
47
    num_of_1[i] = getsum(i);
48
  }
49

50
  n = read(), m = read();
51
  char ch;
52
  for(int i = 0;i < n;i++)
53
  {
54
    for(int j = 0;j < m;j++)
55
    {
56
      cin >> ch;
57
      if(ch == 'H')
58
      {
59
        Map[i] |= (1 << j);
60
      }
61
    }
62
  }
63

64
  for(int j = 0;j < (1 << m);j++)
65
  {
66
    if(j & (j << 1) || j & (j << 2) || j & Map[0]) continue;
67
    f[0][j][0] = num_of_1[j];
68
  }
69

70
  for(int j = 0;j < (1 << m);j++)
71
  {
72
    for(int fl = 0;fl < (1 << m);fl++)
73
    {
74
      if(j & (j << 1) || j & (j << 2) || j & Map[1] || fl & (fl << 1) || fl & (fl << 2) || fl & Map[0] || j & fl || j & Map[1])
75
        continue;
76
      f[1][j][fl] = num_of_1[j] + num_of_1[fl];
77
    }
78
  }
79

80
  for(int i = 2;i < n;i++)
81
  {
82
    for(int j = 0;j <= (1 << m) - 1;j++)//当前行
83
    {
84
      if(j & Map[i] || j & (j << 1) || j & (j << 2))
85
      {
86
        continue;
87
      }
88

89
      for(int fl = 0; fl <= (1 << m) - 1;fl++)//上一行
90
      {
91
        if(fl & Map[i - 1] || fl & (fl << 1) || fl & (fl << 2) || j & fl)
92
        {
93
          continue;
94
        }
95

96
        for(int fll = 0; fll < (1 << m);fll++)
97
        {
98
          if(fll & Map[i - 2] || fll & (fll << 1) || fll & (fll << 2) || j & fll || fl & fll)
99
          {
100
            continue;
101
          }
102

103
          f[i % 3][j][fl] = max(f[i % 3][j][fl], f[(i - 1) % 3][fl][fll] + num_of_1[j]);
104

105
        }
106
      }
107
    }
108
  }
109

110

111
  int ans = 0;
112

113
  for(int j = 0;j < (1 << m);j++)
114
  {
115
    for(int fl = 0;fl < (1 << m);fl++)
116
    {
117
      ans = max(ans, f[(n - 1) % 3][j][fl]);
118
    }
119
  }
120

121
  cout << ans << endl;
122
  return 0;
123
}