今天艾教留了一大堆线段树，表示做不动了，就补补前面的题。QAQ
这个题，我第一次写还是像前面HDU 2167那样写，发现这次影响第 i 行的还用i-2行那样，那以前的方法就行不通了。
找出所有可行的状态，因为每一行最大只有10列，所以一行里最多有4个，那它可行的状态不多(网上大多数说法最多是60个)。用dp[x][i][j]来转移,x表示第x行，i表示第x行的状态，j表示第x-1行的状态。先初始化前两行。
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = ;
#define legal(a,b) (a&b)
int base[maxn];
int state[maxn];
int solders[maxn];
int dp[maxn][maxn][maxn];
char s[maxn][];
int num = ;
int main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i=;i<n;i++)
{
scanf("%s",s[i]);
for(int j=;j<m;j++)
{
if(s[i][j]=='H') base[i]+=(<<j); //记录山地
}
}
int d = ;
for(int i=;i<(<<m);i++) //删除一行中相互攻击的点
{
if(legal(i,i<<)||legal(i,i<<)) continue;
int k = i;
while(k) //记录里面有多少个炮台
{
solders[num]+=(&k);
k=k>>;
}
state[num++] = i;
}
for(int i=;i<num;i++) //初始化第0行
{
if(legal(state[i],base[])) continue;
dp[][i][] = solders[i];
}
for(int i=;i<num;i++) //初始化第1行，此为第二行
{
if(legal(state[i],base[])) continue;
for(int j=;j<num;j++) //枚举第一行
{
if(legal(state[j],base[])) continue;
if(legal(state[i],state[j])) continue;
dp[][i][j] = max(dp[][i][j],dp[][j][]+solders[i]);
}
} for(int r=;r<n;r++) //开始从第二行枚举
{
for(int i=;i<num;i++) //枚举r行
{
if(legal(state[i],base[r])) continue;
for(int j=;j<num;j++) //枚举r-1行
{
if(legal(state[j],base[r-])) continue;
if(legal(state[j],state[i])) continue;
for(int k=;k<num;k++) //枚举第r-2行
{
if(legal(state[k],base[r-])) continue;
if(legal(state[k],state[i])) continue;
if(legal(state[k],state[j])) continue;
dp[r][i][j] = max(dp[r][i][j],dp[r-][j][k]+solders[i]);
}
}
}
}
int maxx = ;
for(int i=;i<num;i++)
{
for(int j=;j<num;j++)
maxx = max(maxx,dp[n-][i][j]);
}
printf("%d\n",maxx);
return ;
}