POJ 1185 经典状压dp

做了很久的题 有注释

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<math.h>
using namespace std;
int dp[107][107][107];///二维记录上一次 三维记录此次
///dp[i][k][j]=max(dp[i][k][j],dp[i-1][t][k])+num[j]; t为枚举数且满足与 k j 的条件
///初始化can num数组减少时间
///如果不使用can数组来记录 memset都会超时
int can[107];
int num[107];
int n,m;
int c[107];
char s[107];
bool ok(int x)
{
    if(x&(x<<1))
        return false;
    if(x&(x<<2))
        return false;
    return true;
}
int main(){
while(~scanf("%d%d",&n,&m))
{
    for(int i=0;i<n;i++)
    {
        scanf("%s",s);
        c[i]=0;
        for(int k=0;k<m;k++)
        {
            if(s[k]=='H')     
                c[i]+=(1<<k);
        }
    }
    int w=0;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<(1<<m);i++)
    {
        if(ok(i))
        {
            can[w]=i;
            int x=can[w];
            num[w]=0;
            while(x>0)
            {
                if(x&1)num[w]++;
                x>>=1;
            }
            w++;
        }
    }
    for(int i=0;i<w;i++)
    {
        if(!(can[i]&c[0])) ///得满足条件才能放
        dp[0][0][i]=num[i];
    }
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<w;j++)
        {
            if(c[i]&can[j])
                continue;
            for(int k=0;k<w;k++)
            {
                if(can[j]&can[k])
                    continue;
                for(int t=0;t<w;t++)
                {
                    if(can[j]&can[t]||can[k]&can[t])
                        continue;
                    if(dp[i-1][t][k]==-1) ///如果上一行等于-1说明不满足条件 
                        continue;
                    dp[i][k][j]=max(dp[i][k][j],dp[i-1][t][k]+num[j]);
                }
            }
        }
    }
    int ans=0;
    for(int k=0;k<n;k++)
    for(int i=0;i<w;i++)
    for(int j=0;j<w;j++)
    {
        ans=max(ans,dp[k][i][j]);
    }
    printf("%d
",ans);
}
}