B

刚开始接触状压dp，感觉就形式上来说还是比较固定的，和数位dp差不多，但是各种位运算还是不够熟练，用起来有点不是得心应手

还是得多练练，这部分代码还不是很好写。

题意: 中文题，不多说了。

思路： dp[n][prestate][preprestate] 表示第n行的时候的状态是由前两行的状态推倒出的

转移方程: dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][t] + num[j]);

接下来就是看代码了，里面注释都有

 1 #include <string.h>
 2 #include <algorithm>
 3 #include <stdio.h>
 4 #include <string>
 5 #include <iostream>
 6 using namespace std;
 7 
 8 int dp[101][1025][1025];
 9 int a[1025];
10 int n, m;
11 int vnum;
12 int num[1025], vst[1025];
13 
14 int getsum(int i) {    // __builtin_popcount(i)
15     int res = 0;
16     while (i) {
17         i &= i - 1;
18         ++res;
19     }
20     return res;
21 }
22 
23 void initialState() {//vst数组记录的是对于每一行符合题目要求的安防方法 num记录的是对应安防方法的安防炮兵个数
24     vnum = 0;
25     for (int i = 0; i < (1 << m); ++i) {
26         if (!(i&(i << 1)) && !(i&(i << 2))) {            
27             vst[vnum] = i;
28             num[vnum++] = getsum(i);
29             cout << vst[vnum - 1] << ends << num[vnum - 1] << endl;
30         }
31     }
32 }
33 
34 int main() {
35     ios::sync_with_stdio(false);
36     while (cin >> n >> m) {
37         for (int i = 0; i < n; ++i) {
38             a[i] = 0;
39             for (int j = 1; j <= m; ++j) {
40                 char c; cin >> c;
41                 a[i] = a[i] * 2 + (c == 'P');
42             }
43         }
44         for (int i = 0; i <= n; ++i)
45             for (int j = 0; j <= 61; ++j)
46                 for (int k = 0; k <= 61; ++k)
47                     dp[i][j][k] = -1;
48         initialState();
49         for (int i = 0; i < vnum; ++i)
50             if (!(vst[i] & (~a[0])))
51                 dp[0][i][0] = num[i];
52         for (int i = 1; i < n; ++i) {
53             for (int j = 0; j < vnum; ++j) {
54                 if ((~a[i]) & vst[j]) continue;            //判断当前行vit[j]中1的集合是不是属于a[i]的集合
55                 for (int k = 0; k < vnum; ++k) {
56                     if ((~a[i - 1])&vst[k]) continue;    //对于上一行同样的判断
57                     if (vst[j] & vst[k]) continue;        //上下相邻两行得符合题目要求
58                     for (int t = 0; t < vnum; ++t) {
59                         if (vst[j] & vst[t]) continue;
60                         if (-1 == dp[i - 1][k][t]) continue;
61                         dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][t] + num[j]); //状态转移方程
62                     }
63                 }
64             }
65         }
66         int res = 0;
67         for (int i = 0; i < vnum; ++i) {
68             for (int j = 0; j < vnum; ++j) {
69                 if (dp[n - 1][i][j] > res)
70                     res = dp[n - 1][i][j];
71             }
72         }
73         cout << res << endl;
74     }
75     return 0;
76 }