POJ_1185_炮兵阵地 dp+状态压缩

2015-12-18 来源: hchlqlz 发布在  https://www.cnblogs.com/hchlqlz-oj-mrj/p/5058059.html

题目:炮兵阵地

链接:http://poj.org/problem?id=1185

解题思路:

  首先用 int 来表示每一行的情况,比如说第一行是k1,那么【 k1&(k1>>2) | k1&(k1>>1) 】就可以排除一行中相邻的和隔一格的。。。

  地形也可以用 int (取反)来表示,比如说第一行是PPHPH,给他记作m1=00101(二进制数),1表示不能存放,那么对于一个数a,判断a是不是符合地形就可以用【 a & m1 】来表示,如果与出来的是真,那么说明存在某一位1&1的情景,就表示不符合。

  下一行是否能和上一行共存也用位运算来进行,比如下一行是s2,上一行是s1,那么【 s2 & s1 】为真就表示不能共存。

  上面是通过位运算来巧妙解决可行存放问题的方法。

  贴代码了:

  

 #include<stdio.h>
 #include<string.h>
 /*
   改进。。。
 */
 ][];
 ];
 ],ao;
 ][][];
 /*
   dp[i][j][k]: 第i行 - 上一行是ans[j]、本行是ans[k]的情况下,最多数量为多少。
   因为有了两行的间隔,上面的炮台就不会影响到下面的,所以只要记录两行的所有情况,两行相同的可以计算出最大值了
 */
 //因为列数最多为10,所以无视地形,一行最多有60中存放方式
 void func(int m)
 {
   ;i<(<<m);i++)
   {
     )||i&(i>>)) continue;
     ans[ao++]=i;
   }
 }
 int count(int x)
 {
   ;
   while(x)
   {
     co+=x&;
     x>>=;
   }
   return co;
 }
 ][],po,ko,lo;
 int main()
 {
   int n,m;
   while(scanf("%d%d",&n,&m)!=EOF)
   {
     ;i<n;i++)
     {
       scanf("%s",s[i]);
     }
     memset(mp,,sizeof(mp));
     ;i<n;i++)
     {
       ;j<m;j++)
       {
         <<j);
       }
     }
     ao=;
     func(m);
     memset(dp,,sizeof(dp));
     po=;
     ;i<ao;i++)
     {
       ]&ans[i]) continue;
       int tmp=count(ans[i]);
       dp[][][i]=tmp;
       pre[][po++]=i;   //记录第0行所有存值情况,po为总数
     }
     )
     {
       ;
       ;i<po;i++)
       {
         ][i];  //因为前面只有一行,所以只需要考虑pre[0][i]的情况
         ][][line1]>mt) mt=dp[][][line1];
       }
       printf("%d\n",mt);
       continue;
     }
     ko=;
     ;i<po;i++)
     {
       ;j<ao;j++)
       {
         ][i];
         ]) continue;
         if(ans[line1]&ans[j]) continue;
         int tmp=count(ans[j]);
         dp[][line1][j]=dp[][][line1]+tmp;
         pre[][ko]=line1;  //到下一行时,这里就是上两行,下面的就是上一行,先用2暂存,最终再移入0
         pre[][ko++]=j;
       }
     }
     ;i<ko;i++)
       pre[][i]=pre[][i];
     ][];
     ;i<n;i++)
     {
       lo=;
       memset(v,,sizeof(v));
       ;k<ko;k++)
       {
         ][k],line2=pre[i-][k];   //上两行和上一行的情况
         if(v[line1][line2]) continue;     //因为有很多重复的,去重
         v[line1][line2]=;
         ;u<ao;u++)
         {
           if(ans[u]&mp[i]) continue;  //如果与本身的地形不符,就跳过
           if(ans[u]&ans[line1]||ans[u]&ans[line2]) continue;  //如果和前两行矛盾就跳过
           int tmp=count(ans[u]);      //如果都满足条件,就计算这一行这种放法增加的数量
           ][line1][line2]+tmp>dp[i][line2][u])
           {
             dp[i][line2][u]=dp[i-][line1][line2]+tmp;
             pre[i+][lo]=line2;       //先用i+1的存放,等k的循环结束再移到i-1
             pre[i][lo++]=u;
           }
         }
       }
       ;u<lo;u++)
         pre[i-][u]=pre[i+][u];
       ko=lo;
     }
     ;
     ;j<ko;j++)
     {
       ][j],line2=pre[n-][j];
       ][line1][line2]) mt=dp[n-][line1][line2];
     }
     printf("%d\n",mt);
   }
   ;
 }

相关文章