学步园

题目：

http://poj.org/problem?id=1185

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define INF 0xfffffff
using namespace std;

int dp[109][60][60],h[109],cnt,s[1<<10],num1[1<<10],n,m;

int num(int k)
{
    int ans=0;
    while(k>0) k&=(k-1),ans++;
    return ans;
}

bool can(int k)
{
    if(k&(k<<1)) return false;
    if(k&(k<<2)) return false;
    return true;
}
int print(int k,int m=m)
{
    if(m<=0) return 2;
    print(k>>1,m-1);
    cout<<(k&1);
    if(m==::m) cout<<"       ";
    return 2;
}

void DP()
{
    int i,j,k1,k2,k;
    memset(dp,-1,sizeof(dp));
    for(j=0;j<cnt;j++) if((s[j]&h[0])==0) dp[0][j][0]=num1[j];
    for(i=1;i<n;i++)
    {
        for(j=0;j<cnt;j++) if((s[j]&h[i])==0)
        {
            for(k1=0;k1<cnt;k1++) if((s[k1]&s[j])==0)
            {
                for(k2=0;k2<cnt;k2++) if((s[k2]&s[j])==0)
                {
                    if(dp[i-1][k1][k2]>=0) dp[i][j][k1]=max(dp[i][j][k1],dp[i-1][k1][k2]+num1[j]);
                }
            }
        }
    }
}

int main()
{
    //freopen("in.txt","r",stdin);
    while(cin>>n>>m)
    {
        int i,j,k,k1,k2;
        char c;
        cnt=0;
        for(k=0;k<(1<<m);k++) if(can(k))
        {
            s[cnt]=k;
            num1[cnt]=num(k);
            cnt++;
        }
        for(i=0;i<n;i++)
        {
            h[i]=0;
            for(j=0;j<m;j++)
            {
                cin>>c;
                h[i]<<=1;
                if(c=='H') h[i]|=1;
            }
        }
        for(i=0;i<n;i++) for(j=0;j<cnt;j++) for(k=0;k<cnt;k++) dp[i][j][k]-=INF;
        DP();
        int ans=0;
        for(j=0;j<cnt;j++) for(k=0;k<cnt;k++) ans=max(ans,dp[n-1][j][k]);
        cout<<ans<<endl;
    }
    return 0;
}