poj 1185 炮兵阵地 （状态压缩dp）

代码

       #include <stdio.h>
       #include <string.h>
       #include <algorithm>
       using namespace std;
       const int maxn = 62;          //每行合法的状态总共有61种
       int dp[102][maxn][maxn];      //因为状态是与前两行有关，所以用到三维数组
       int sta[102];                 //每行不能放置的点
       int cnt[maxn];                //状态中1的数目，也就是炮的数目
       int allsta[maxn];             //所有可能的状态
       int n, m;
       int num;                      //满足条件的状态数
       bool judgeself(int x) //判断x状态是不是有会相互攻击的状态，也就是有没有两个1相隔少于两个0
       {
          if (x&(x<<1) || x&(x<<2))
              return false;
          return true;
       }
       int count(int x) //用很巧妙的计算出x二进制中1的个数
       {
          int s = 0;
          while (x)
           {
               s++;
               x = x&(x-1);
           }
          return s;
       }
       void search(int x)
       {                                   //这个函数相当于把对状态进行了离散化，去掉了每行所有不合法的状态
          int t = 1<<x;
           num = 0;
          for (int i = 0; i < t; i++)
           {
              if (judgeself(i))
               {
                   allsta[num] = i;
                   cnt[num] = count(i);
                   num++;
               }
           }
       }
       bool fit(int x, int y)
       {
          if(x&y)
              return false;
          return true;
       }
       void getresult()
       {
          memset(dp, 0, sizeof(dp));
          for (int i = 0; i < num; i++)              //因为计算每行的时候需要用到前两行的状态，需要对第一行特殊处理
           {
              for (int j = 0; j < num; j++)
               {
                  if (fit(sta[1], allsta[i]) && fit(allsta[i], allsta[j]))
                       dp[1][j][i] = cnt[i];
               }
           }
          for (int i = 2; i <= n; i++)
           {
              for (int j = 0; j < num; j++)
               {
                  if (!fit(sta[i], allsta[j]))
                      continue;
                  for (int k = 0; k < num; k++)
                   {
                      if (!fit(allsta[j], allsta[k]))           // 判断是否与前一行冲突
                          continue;
                      for (int l = 0; l < num; l++)
                       {
                          if (!fit(allsta[j], allsta[l]))       //不光要判断是否与前一行冲突，要判断第前两行
                              continue;
                           dp[i][k][j] = max(dp[i][k][j], dp[i-1][l][k]+cnt[j]);
                       }
                   }
               }
           }
          int ans = 0;
          for (int i = 0; i < num; i++)
           {
              for (int j = 0; j < num; j++)
               {
                  if (!fit(allsta[i], allsta[j]))
                      continue;
                   ans = max(ans, dp[n][i][j]);              //求出最后一行最大的结果
               }
           }
          printf("%d\n", ans);
       }
       int main()
       {
          while (scanf("%d %d", &n, &m) != EOF)
           {
              memset(sta, 0, sizeof(sta));
              search(m);
              for (int i = 1; i <= n; i++)
               {
                  getchar();
                  for (int j = 1; j <= m; j++)
                   {
                      char t;
                      scanf("%c", &t);
                      if (t == 'H')
                           sta[i] += (1<<(m-j));            //标记一行中不能安放炮兵的状态
                   }
               }
              getresult();
           }
          return 0;
       }