POJ 1185 炮兵阵地

主要还是下面的解题报告写的。
http://blog.csdn.net/accry/article/details/6607703
贴代码，代码中有一些注释
  1 #include <cstdio>
  2 #include <cstring>
  3 int map[105];
  4 int st[70];
  5 int n,m;
  6 int dp[105][70][70];
  7 int one[70];
  8 
  9 //数x化为二进制时1的个数
 10 int countOne(int x)
 11 {
 12     int cnt =0;
 13     while(x)
 14     {
 15         ++cnt;
 16         x &= (x-1);
 17     }
 18     return cnt;
 19 }
 20 int max(int a,int b)
 21 {
 22     return a>b?a:b;
 23 }
 24 
 25 //检查横向情形
 26 bool checkHori(int a)
 27 {
 28     if(a & (a << 1)) return false;
 29     if(a & (a << 2)) return false;
 30     return true;
 31 }
 32 //读入数据
 33 void scan()
 34 {
 35     for(int i=1; i<=n; ++i)
 36     {
 37         char str[12];
 38         int tmp =1;
 39         map[i] = 0;
 40         scanf("%s",str);
 41         for(int j=0; j<m; ++j)
 42         {
 43             if(str[j] == 'H')  //'P'为0,'H'为1,技巧
 44                 map[i] += tmp;
 45             tmp *=2;
 46         }
 47     }
 48 }
 49 
 50 int init(int m)
 51 {
 52     int num=0;
 53     for(int i=0; i<(1<<m); ++i)
 54     {
 55         if(checkHori(i))
 56         {
 57             st[num] = i;
 58             one[num] = countOne(i);
 59             ++num;
 60         }
 61     }
 62     return num;
 63 }
 64 int main()
 65 {
 66 //    freopen("in.cpp","r",stdin);
 67     scanf("%d%d",&n,&m);
 68     scan();
 69     countOne(m);
 70     int num = init(m);
 71     memset(dp,-1,sizeof(dp));//表示不合理状态
 72     //初始化第一行，人为添加第0行，第0行可行状态只为0==st[0]
 73     for(int i=0; i<num; ++i)
 74     {
 75         if(st[i] & map[1]) continue;
 76         dp[1][0][i] = one[i];
 77     }
 78     for(int i=2; i<=n; ++i)
 79     {
 80         for(int j3 =0; j3 < num; ++j3)
 81         {
 82             if(map[i] & st[j3] ) continue;//检查当前状态与该行实际地形是否匹配,是否在山地上架了炮
 83             for(int j2=0; j2 < num; ++j2)
 84             {
 85                 if(st[j2] & st[j3]) continue;  //纵向检查
 86                 for(int j1 = 0; j1 < num; ++j1)
 87                 {
 88                     if(st[j1] & st[j3]) continue;//纵向检查
 89                     if(dp[i-1][j1][j2] == -1) continue; //这种状态不存在
 90                     dp[i][j2][j3] =max(dp[i-1][j1][j2]+one[j3] , dp[i][j2][j3]);
 91                 }
 92             }
 93         }
 94     }
 95     int ans =0;
 96     for(int k=0; k<=n; ++k)
 97         for(int i=0; i<num; ++i)
 98             for(int j=0; j<num; ++j)
 99                 ans =max(dp[k][i][j] , ans);
100     printf("%d
",ans);
101     return 0;
102 }
View Code