题目：炮兵阵地
链接：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>
/*
改进。。。
*/
char s[][];
int mp[];
int ans[],ao;
int dp[][][];
/*
dp[i][j][k]: 第i行 - 上一行是ans[j]、本行是ans[k]的情况下，最多数量为多少。
因为有了两行的间隔，上面的炮台就不会影响到下面的，所以只要记录两行的所有情况，两行相同的可以计算出最大值了
*/
//因为列数最多为10，所以无视地形，一行最多有60中存放方式
void func(int m)
{
for(int i=;i<(<<m);i++)
{
if(i&(i>>)||i&(i>>)) continue;
ans[ao++]=i;
}
}
int count(int x)
{
int co=;
while(x)
{
co+=x&;
x>>=;
}
return co;
}
int pre[][],po,ko,lo;
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=;i<n;i++)
{
scanf("%s",s[i]);
}
memset(mp,,sizeof(mp));
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
if(s[i][j]=='H') mp[i]=mp[i]|(<<j);
}
}
ao=;
func(m);
memset(dp,,sizeof(dp));
po=;
for(int i=;i<ao;i++)
{
if(mp[]&ans[i]) continue;
int tmp=count(ans[i]);
dp[][][i]=tmp;
pre[][po++]=i; //记录第0行所有存值情况，po为总数
}
if(n==)
{
int mt=;
for(int i=;i<po;i++)
{
int line1=pre[][i]; //因为前面只有一行，所以只需要考虑pre[0][i]的情况
if(dp[][][line1]>mt) mt=dp[][][line1];
}
printf("%d\n",mt);
continue;
}
ko=;
for(int i=;i<po;i++)
{
for(int j=;j<ao;j++)
{
int line1=pre[][i];
if(ans[j]&mp[]) 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;
}
}
for(int i=;i<ko;i++)
pre[][i]=pre[][i];
bool v[][];
for(int i=;i<n;i++)
{
lo=;
memset(v,,sizeof(v));
for(int k=;k<ko;k++)
{
int line1=pre[i-][k],line2=pre[i-][k]; //上两行和上一行的情况
if(v[line1][line2]) continue; //因为有很多重复的，去重
v[line1][line2]=;
for(int u=;u<ao;u++)
{
if(ans[u]&mp[i]) continue; //如果与本身的地形不符，就跳过
if(ans[u]&ans[line1]||ans[u]&ans[line2]) continue; //如果和前两行矛盾就跳过
int tmp=count(ans[u]); //如果都满足条件，就计算这一行这种放法增加的数量
if(dp[i-][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;
}
}
}
for(int u=;u<lo;u++)
pre[i-][u]=pre[i+][u];
ko=lo;
}
int mt=;
for(int j=;j<ko;j++)
{
int line1=pre[n-][j],line2=pre[n-][j];
if(mt<dp[n-][line1][line2]) mt=dp[n-][line1][line2];
}
printf("%d\n",mt);
}
return ;
}