POJ 1185 炮兵阵地 三维DP *

题目地址：http://poj.org/problem?id=1185

dp[i][j][k]表示第i行布局为j,第i-1行布局为k时,前i行的最多炮兵数目。
1）j,k这两种布局必须相容。否则 dp[i][j][k] = 0
2) dp[i][j][k] = max{dp[i-1][k][m], m = 0...1023} + Num(j),
Num(j)为布局j中炮兵的数目, j和m必须相容, k和m必须相容。此时满足无
后效性
3) 初始条件：
dp[0][j][0] = Num(j)
dp[1][i][j] = max{dp[0][j][0]} + Num(i)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cmath>
#include<cstring>
using namespace std;
int n,m;
int G[100+5];
int d[100+5][70][70];
//d[i][j][k]第i行布局为j，第i-1行布局为k，前i行最多炮兵数 
int state[70],nState=0;
bool done[10+5]={false};
bool vis[1030]={false};
int Num[70]={0};
void DFS()
{for(int i=0;i<m;i++){bool ok=true;for(int j=-2;j<=2;j++)if(i+j>=0&&i+j<m&&done[j+i]) ok=false;if(ok){done[i]=true;DFS();done[i]=false;}}int s=0,cnt=0;for(int i=0;i<m;i++)if(done[i]) {s|=(1<<i);cnt++;}if(!vis[s]) {state[nState]=s;Num[nState]=cnt;nState++;}vis[s]=true;
}bool inline bSPut(int i,int j){  //state[i]和state[j]匹配 return (state[i]&state[j])==0;
}
bool inline bGPut(int row,int s){ //state[s]能被放在row上 return (G[row]&state[s])==0;
} 
int main()
{cin>>n>>m;DFS(); char str[10+5];for(int i=0;i<n;i++){scanf("%s",str);for(int j=0;str[j];j++)if(str[j]=='H') G[i]+=pow(2,m-j-1);}for(int i=0;i<nState;i++) {if(bGPut(0,i)) d[0][i][0]=Num[i];}for(int i=0;i<nState;i++)for(int j=0;j<nState;j++)if(bGPut(1,i)&&bGPut(0,j)&&bSPut(i,j)) d[1][i][j]=max(d[1][i][j],d[0][j][0]+Num[i]);for(int i=2;i<n;i++){for(int j=0;j<nState;j++) {if(bGPut(i,j))for(int k=0;k<nState;k++){if(bGPut(i-1,k)&&bSPut(j,k))for(int m=0;m<nState;m++)if(bGPut(i-2,m)&&bSPut(k,m)&&bSPut(j,m))d[i][j][k]=max(d[i][j][k],d[i-1][k][m]+Num[j]);} }}int ans=0;for(int i=0;i<nState;i++)for(int j=0;j<nState;j++)ans=max(ans,d[n-1][i][j]);cout<<ans;return 0;
}