POJ 1185 炮兵阵地

　　经典状态压缩动态规划。

　　由于每个炮兵的位置影响范围为2的行和列，导致状态很难表示，但我们注意到最多有10列，我们可以先对行进行状态压缩，由于m <= 10，则每一行最多只有60种状态（这些状态暴力枚举去除不符合的即可）。由于每个炮兵对其所在列有大小为2的竖直方向的影响范围，那么，显然，我们得开一个三维dp数组，分析得到转移方程为：

　　dp[i, k1, k2] = MAX{dp[i-1, k2, k3] + b[k1]}

　　这条转移方程的dp[i, k1, k2]表示第i行选择第 k1 种状态，第i-1行选择第 k2 种状态时最多能安排的炮兵数，b[k1]为第 k1 种状态的二进制表示的1的个数。

　　状态压缩与位运算息息相关，一下两点对于题目求解有很大的帮助：

1. 第i行放第k1种状态，第i-1行放第k2种状态，会不会出现矛盾

对于状态a[k1]和a[k2],如果他们是可行的，讨论他们每个对应的位置

　　　 a[k1]如果某位置是1,a[k2]这位上必须是0

　　 a[k1]如果某位置是0,a[k2]这位上可以是1，也可以是0

　　　所以可以归纳出 a[k1] & a[k2] = 0，这要判断矛盾可以使速度大大提高

　　2. 对于每一行，第i种状态能不能放上去，即要求不能在‘H’的地方放士兵

　　　我们可以先把每行原来的初始状态也表示出来，但是这里有个小技巧，把‘H’的地方记录下来

　　　这行如果某位置是1，那么在a[k1]中这个位置上必须为0（1代表这里是山地）

　　　这行如果某位置是0，那么在a[k1]中这个位置上可以为1，可以为0（0代表这里是平原）

　　　所以可以归纳出 now[i] & a[k1]=0

　　状态压缩DP就是充分利用位运算降低时间复杂度的一种优化。

View Code

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <string>
  5 #include <algorithm>
  6 using namespace std;
  7 const int maxn = 100 + 5;
  8 const int maxm = 60 +5;
  9 int n, m, k;
 10 char s[maxn][maxm];
 11 int dp[maxn][maxn][maxn];
 12 int a[maxn];      // 压缩后的状态值
 13 int b[maxn];      // 每个状态二进制表示中1的个数
 14 int now[maxn];    // 每行地形对应的值，二进制表示，1表示'H'，0表示'P'
 15 
 16 bool check1(int v)   // 去掉含有“11”的数
 17 {
 18     for(int i = 0; i < m-1; i++)
 19     {
 20         if(((v >> i) & 1) && ((v >> (i+1)) & 1))
 21             return false;
 22     }
 23     return true;
 24 }
 25 
 26 bool check2(int v)   // 去掉含有“101”的数
 27 {
 28     for(int i = 0; i < m - 2; i++)
 29     {
 30         if(((v >> i) & 1) && ((v >> (i + 2)) & 1))
 31             return false;
 32     }
 33     return true;
 34 }
 35 
 36 void getB(int v)
 37 {
 38     for(int i = 0; i < m; i++)
 39         b[k] += (v >> i) & 1;
 40     k++;
 41 }
 42 
 43 void getA()
 44 {
 45     for(int i = 0; i < (1 << m); i++)  // 暴力枚举行状态
 46     {
 47         if(check1(i) && check2(i))
 48         {
 49             a[k] = i;
 50             getB(i);
 51         }
 52             
 53     }
 54 }
 55 
 56 void DP()
 57 {
 58     for(int i = 1; i <= n; i++)
 59     {
 60         for(int k1 = 0; k1 < k; k1++)
 61         {
 62             if(!(now[i] & a[k1]))
 63             {
 64                 for(int k2 = 0; k2 < k; k2++)
 65                 {    
 66                     if(!(a[k1] & a[k2]))
 67                     {
 68                         for(int k3 = 0; k3 < k; k3++)
 69                         {    
 70                             if(!(a[k1] & a[k3]))
 71                                 dp[i][k1][k2] = max(dp[i][k1][k2], dp[i-1][k2][k3] + b[k1]);
 72                         }
 73                     }
 74                 }
 75             }
 76         }
 77     }
 78 }
 79 
 80 void init()
 81 {
 82     k = 0;
 83     memset(now, 0, sizeof now);
 84     memset(dp, 0, sizeof dp);
 85 }
 86 
 87 void input()
 88 {
 89     for(int i = 1; i <= n; i++)
 90     {
 91         scanf("%s", s[i]);
 92         for(int j = 0; s[i][j]; j++)
 93             now[i] |= (s[i][j] == 'H') << j;
 94     }
 95 }
 96 
 97 void output()
 98 {
 99     int ans = 0;
100     for(int k1 = 0; k1 < k; k1++)
101         for(int k2 = 0; k2 < k; k2++)
102             ans = max(ans, dp[n][k1][k2]);
103     printf("%d\n", ans);
104 }
105 
106 int main()
107 {
108     while(scanf("%d %d", &n, &m) != EOF)
109     {
110         init();
111         getA();
112         input();
113         DP();
114         output();
115     }
116     return 0;
117 }