http://poj.org/problem?id=1185
状压DP:
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 int dp[105][100][100]; 7 int ma[105],st[105]; 8 9 int ok(int x) 10 { 11 return (x&(x<<1))+(x&(x<<2)); 12 } 13 14 int num(int x) 15 { 16 int sum=0; 17 while (x) 18 { 19 if (x&1) sum++; 20 x>>=1; 21 } 22 return sum; 23 } 24 int main() 25 { 26 int n,m,i,j,k,l; 27 char c; 28 cin>>n>>m; 29 memset(dp,0,sizeof(dp)); 30 memset(ma,0,sizeof(ma)); 31 for (i=1;i<=n;i++) 32 { 33 for (j=1;j<=m;j++) 34 { 35 cin>>c; 36 if (c=='H') ma[i]+=1<<(j-1); 37 } 38 } 39 int cut=0; 40 for (i=0;i<(1<<m);i++) 41 { 42 if (!ok(i)) st[cut++]=i; 43 } 44 for (i=0;i<cut;i++) 45 { 46 if (!(ma[1]&st[i])) dp[1][i][0]=num(st[i]); 47 } 48 for (i=2;i<=n;i++) 49 { 50 for (j=0;j<cut;j++) 51 { 52 if (ma[i]&st[j]) continue; 53 for (k=0;k<cut;k++) 54 { 55 if (ma[i-1]&st[k]) continue; 56 if (st[k]&st[j]) continue; 57 for (l=0;l<cut;l++) 58 { 59 if (ma[i-2]&st[l]) continue; 60 if (st[l]&st[j]) continue; 61 if (st[k]&st[l]) continue; 62 dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][l]+num(st[j])); 63 } 64 } 65 } 66 } 67 int ans=0; 68 for (i=0;i<cut;i++) 69 { 70 for (j=0;j<cut;j++) ans=max(ans,dp[n][i][j]); 71 } 72 cout<<ans<<endl; 73 }