做题感悟：这题开始想了很久都没想到怎样解决，百度了一下才明白，真的很经典。
解题思路：
解决这种题首先思考一下当前状态（这里设为 i ）与哪些状态有关 ？ 这题很明显当前状态 i 与 i - 1 , i - 2 有关，so ~ 当操作当前状态时必须从 i - 1 和 i - 2 的 状态转化，你也许想到用 dp [ i ][ S(i - 1) ] [ S (i - 2) ] [ Si ] 来做，但是完全可以用
dp [ i ] [ S( i - 1 ) [ Si ] = max( dp [ i ] [ S( i - 1 ) ] [ Si ] , dp [ i - 1 ] [ S( i - 2 ) ] [ i - 1 ] ) ;
其实只需要三维 dp 就可以了。做的时候要先处理一下每种状态是否满足行的要求，边界条件为 dp [ 1 ] [ 1 ] [ i ] = num [ i ] ; i 代表第 i 种状态。
代码：
#include<stdio.h>
#include<queue>
#include<cmath>
#include<string.h>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stdlib.h>
using namespace std ;
const int MY = 100 + 10 ;
const int MX = 100 + 10 ;
int n , m , S , p ;
char s[MX][MX] ;
int dp[MX][MX][MX] , a[MX] , num[MX] , key[MX] ;
bool judge(int x) // 判断同行是否可行
{
if((x & (x << 1))||(x & (x << 2)))
return false ;
return true ;
}
void init()// 初始化
{
S = 1<<m ;
p = 1 ;
for(int i = 0 ;i < S ; i++)
if(judge(i))
key[p++] = i ;
}
int count(int x) // 计算 1 的个数
{
int sum=0 ;
while(x)
{
x &= (x-1) ;
sum++ ;
}
return sum ;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
init() ;
for(int i = 1 ; i <= n ; i++)
cin>>(s[i] + 1) ;
for(int i= 1 ; i <= n ; i++)
{
a[i]=0 ; // i 中的不合法状态
for(int j = 1 ; j <= m ; j++)
if(s[i][j]=='H')
a[i] |= 1<<(j - 1) ;
}
memset(dp,-1,sizeof(dp)) ;
int ans = 0 ;
for(int i = 1 ; i < p ; i++) // 初始化第一行
{
num[i]=count(key[i]) ; // 计算 1 的个数
if(!(key[i] & a[1])) // 判断是否建在山地上
{
dp[1][1][i] = num[i] ;
ans = max(num[i] , ans) ;
}
}
for(int i = 2 ; i <= n ; i++)
for(int j = 1 ; j < p ; j++)
{
if(key[j] & a[i]) continue ; // 判断是否健在山地上
for(int t = 1 ; t < p ; t++) // 判断与上一行是否冲突
{
if(key[j] & key[t]) continue ;
for(int k = 1 ; k < p ; k++) // 判断与上上一行是否冲突
{
if(key[j] & key[k]) continue ;
if(dp[i-1][t][k] == -1) continue ;
dp[i][k][j] = max(dp[i][k][j] , dp[i-1][t][k] + num[j]) ;
ans = max(dp[i][k][j] , ans) ;
}
}
}
cout<<ans<<endl ;
}
return 0 ;
}