状压DP。因为m<=10，所以把每一行部署炮兵部队的状态作为“状态”，二进制的每一位1表示部署，0表示没有。同时把山地表示为1，平原表示为0，第i行的地形为dx[i]。

因为从上到下考虑，考虑第i行时要考虑第i-1，i-2行，而考虑i-1行时又要考虑第i-2，i-3行……所以令f[i][j][k]表示前i行，第i行状态为j，第i-1行状态为k时可以部署炮兵部队的最大值。

可得以下方程：

$f[i][j][k]=\max(f[i-1][k][l]+cnt[j])(j,k,l\in S , j&k==0,k&l==0,j&dx[i]==0)$

S为一个行状态的合法集合，即状态中“1”两两之间间隔超过2。若一个状态i满足

!(i&(i<<1))&&!(i&(i<<2))

那么i是合法状态。

答案：

$\max(f[n][i][j])(i,j\in S , i&j==0)$

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,s[102],cnt[102],tot;//s是可用集合，cnt是1的数目 
int f[102][72][72];//f的2、3维都是可用状态的编号
//经试验m=10时|s|=60，所以可以放心少开 
int dixing[102];//0平原，1山地，状态&地形!=0即炮兵在山地上 
char str[13];
void input()//输入O(nm) 
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%s",str);
        for(int j=0;j<m;++j)
        {
            dixing[i]<<=1;
            if (str[j]=='H')
                dixing[i]|=1;
        }
    }
}
int count1(int x)//计算1的个数 
{
    int sum=0;
    while(x) x-=x&-x,++sum;
    return sum;
}
void prework()//预处理合法集合O(2^m) 
{
    for(int i=0;i<1<<m;++i)
        if (!(i&(i<<1))&&!(i&(i<<2)))
        {
            s[++tot]=i;
            cnt[tot]=count1(i);//计算1的个数 
        }
}
int main()
{
    input();
    prework();
    memset(f,0xcf,sizeof(f));//f数组初始化 
    f[0][1][1]=0;
    for(int i=1;i<=n;++i)//DP O(n|s|^3) 
    for(int j=1;j<=tot;++j)
    for(int k=1;k<=tot;++k)
    for(int l=1;l<=tot;++l)
    if ((s[j]&s[k])==0&&(s[j]&s[l])==0&&(s[j]&dixing[i])==0)
        f[i][j][k]=max(f[i-1][k][l]+cnt[j],f[i][j][k]);
    int ans=0;//寻找答案 
    for(int i=1;i<=tot;++i)
        for(int j=1;j<=tot;++j)
            ans=max(f[n][i][j],ans);
    printf("%d",ans);
    return 0;
}

View Code