是中国标题。大家都说水问题。但是，良好的1A它？
标题效果：
给出n*m的矩阵，当某个单元格有炮兵部队时它的上下左右两格（不包含斜着的方向）是这支部队的攻击范围。问在两支部队之间不可能相互攻击到的情况下。最多能部署多少炮兵部队。
解题思路：
状态压缩DP，DP[i][j][k]代表当第i行是第j种状态时。第i-1行是第k种状态时，布置炮兵的最大数量。
状态能够预先处理出来，仅仅有60种。
以下是代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
using namespace std;
int min(int a,int b)
{
if(a>b)a=b;
return a;
}
int max(int a,int b)
{
if(a<b)a=b;
return a;
}
int n,m,vaild[65],cn[65],cnt;
void judge()
{
int p,num;
cnt=0;
for(int i=0; i<1<<10; i++)
{
if(((i<<1)&i)||((i<<2)&i))
{
continue;
}
int temp=i;
while(temp)
{
if(temp%2)cn[cnt]++;
temp>>=1;
}
vaild[cnt++]=i;
}
}
int place[105];
char s[15];
int dp[105][65][65];
int main()
{
judge();
while(scanf("%d%d",&n,&m)!=EOF)
{
int ans=0;
for(int i=1; i<=n; i++)
{
scanf("%s",s);
place[i]=0;
for(int j=0; j<m; j++)
{
place[i]<<=1;
if(s[j]=='H')
{
place[i]++;
}
}
}
memset(dp,0,sizeof(dp));
for(int i=1; i<=n; i++)
{
if(i==1)
{
for(int j=0; vaild[j]<1<<m&&j<cnt; j++)
{
if((place[1]&vaild[j])==0)
{
dp[1][j][0]=cn[j];
}
ans=max(ans,dp[1][j][0]);
}
}
else if(i==2)
{
for(int j=0; vaild[j]<1<<m&&j<cnt; j++)
{
if((place[2]&vaild[j])==0)
{
for(int k=0; vaild[k]<1<<m&&k<cnt; k++)
{
if((vaild[k]&vaild[j])==0&&(place[1]&vaild[k])==0)
{
dp[2][j][k]=dp[1][k][0]+cn[j];
}
ans=max(ans,dp[2][j][k]);
}
}
}
}
else
{
for(int j=0; vaild[j]<1<<m&&j<cnt; j++)
{
if((place[i]&vaild[j])==0)
{
for(int k=0; vaild[k]<1<<m&&k<cnt; k++)
{
if((vaild[k]&vaild[j])==0&&(place[i-1]&vaild[k])==0)
{
for(int l=0;vaild[l]<1<<m&&l<cnt;l++)
{
if((vaild[k]&vaild[l])==0&&(vaild[j]&vaild[l])==0&&(place[i-2]&vaild[l])==0)
{
dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][l]+cn[j]);
}
}
}
ans=max(ans,dp[i][j][k]);
}
}
}
}
}
printf("%d\n",ans);
}
return 0;
}