# poj 1185 炮兵阵地

Description

Input

Output

Sample Input

5 4
PHPP
PPHH
PPPP
PHPP
PHHP
Sample Output

6

f[i][j][k]表示前i行，本行状态为j号，上行为k号，j,k是初始化出来的存状态的数组的编号；

#include <cstdio>
int maxs,f[110][110][110],map[110],sa[110],nu[110],n,m,tot;
void dfs(int now,int sat,int num,int le1,int le2)
{
if (now>m)
{
sa[++tot]=sat,
nu[tot]=num;
return;
}
for (int i=0;i<=1;++i)
if (i<=1-le1 && i<=1-le2)
dfs(now+1,sat+i*(1<<now-1),num+i,le2,i);
}
main()
{
scanf("%d%d",&n,&m);
for (register int i=1;i<=n;++i)
{
register char c=getchar();
while(c!='H'&&c!='P')
c=getchar();
register int j=1;
while(c=='H'||c=='P')
{
if (c=='H')
map[i]+=j;
j<<=1,
c=getchar();
}
}
dfs(1,0,0,0,0);
for (register int i=1;i<=n;++i)
for (register int j=1;j<=tot;++j)
if (!(sa[j]&map[i]))
for (register int k=1;k<=tot;++k)
if (!(sa[j]&sa[k])&&!(sa[k]&map[i-1]))
for (register int l=1;l<=tot;++l)
if (!(sa[j]&sa[l])&&!(sa[l]&map[i-2]))
if (f[i][j][k]<f[i-1][k][l]+nu[j])
f[i][j][k]=f[i-1][k][l]+nu[j];
for(register int i=1;i<=tot;++i)
for(register int j=1;j<=tot;++j)
if(f[n][i][j]>maxs)
maxs=f[n][i][j];
printf("%d",maxs);
}