题意：中文题。
思路，经典的状态压缩题目。
由于列长比较小，我们可以以行为阶段用状态压缩来做。
由于攻击只占两个格，这样从行的角度看，第i行的炮兵只与前i-1和前i-2行有关系。这样如果用j，k，l分别表示第i，i-1，i-2行的炮兵摆放状态，而num[i][j]表示第i个摆放状态为j时的炮兵个数。dp[i][k][j]表示以i为最后一行，倒数第一行摆放为j，倒数第二行摆放为k时的最优解。
这样得到状态转移方程dp[i][k][j]=max{dp[i-1][l][k]+num[i][j]}，前提是j和k、l都不互相攻击。
其中炮兵的摆放状态要预处理出来，如果m至大为10，这样枚举的话最多是2^10。由于最后得到合法状态不多，使用的时候可以直接用保存的下标而不是用二进制表示状态。这样可以大大提高时空复杂度。
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<vector>
using namespace std;
vector<];
vector<];
][];
int m,n;
bool check(int sta,int d)
{
<<d);
}
bool check1(int c,int sta)//检查是否在山上放炮
{
; i<m; ++i)
if(grid[c][i]=='H'&&check(sta,i))
return false;
return true;
}
bool attack(int d,int sta)//某状态下判断同行之间是否相互攻击
{
>=&&check(sta,d-)) return true;
>=&&check(sta,d-)) return true;
<m&&check(sta,d+)) return true;
<m&&check(sta,d+)) return true;
return false;
}
int check2(int sta)//判断是否互相攻击和统计炮个数
{
;
; i<m; ++i)
if(check(sta,i))
{
;
else cnt++;
}
return cnt;
}
void init(int c)
{
; i<(<<m); ++i)
if(check1(c,i))//没有放在山坡上的情况
{
int cnt=check2(i);//判断是否互相攻击和炮个数
)
{
sta[c].push_back(i);//保存摆放位置状态
num[c].push_back(cnt);//保存对应状态下的个数
}
}
}
][][];
bool attack2(int sta1,int sta2)//判断不同行之间的状态下炮是否互相攻击
{
; i<m; ++i)
if(check(sta1,i)&&check(sta2,i)) return true;
return false;
}
int main()
{
scanf("%d%d",&n,&m);
; i<=n; ++i)
{
scanf("%s",grid[i]);
init(i);
}
)
{
;
;i<sta[].size();++i)
ans=max(ans,num[][i]);
printf("%d\n",ans);
;
}
; i<sta[].size(); ++i)
; j<sta[].size(); ++j)
][i],sta[][j]))
dp[][i][j]=num[][i]+num[][j];
; i<=n; ++i)
{
; k<sta[i].size(); ++k)
; j<sta[i-].size(); ++j)
{
][j];
if(!attack2(stak,staj))
{
;
; l<sta[i-].size(); ++l)
{
][l];
if(!attack2(stak,stal)&&!attack2(staj,stal))
maxn=max(maxn,dp[i-][l][j]);
}
dp[i][j][k]=maxn+num[i][k];
}
}
}
;
; i<sta[n].size(); ++i)
; j<sta[n-].size(); ++j)
ans=max(ans,dp[n][j][i]);
printf("%d\n",ans);
;
}