poj1185 [NOI2001]炮兵阵地

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

三维装压dp，压缩上一行状态与本行状态，枚举上两行状态转移

第一维可以滚掉，实际复杂度只枚举符合情况的情况，每行状态不会超过60并非$2^M$，（然而luogu还是跑T了），证明参见组合数

#include<cstdio>
#include<cstring>
#include<algorithm>const int maxnm = ;
const int maxn = ;
int n,m;
char a[maxn];
int cant[maxn*];
int map[][];
bool check(int x,int i) {
    if(x&cant[i])return false;
    if(x&(x<<)||x&(x<<))return false;
    return true;
}
int dp[][<<maxn][<<maxn];
int num[<<maxn];
int main( ) {
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;++i)  {
        scanf("%s",a) ;
        for(int j=;j<m;++j)
            if(a[j]=='H')
            cant[i]|=(<<j);
    }
    int po=(<<m)-;
    for(int k,i=;i<=po;++i) {
        if(!check(i,))continue;
        k=i;while(k) {
            num[i]+=(k&);
            k>>=;
        }
    }
    int ans=-;
    for(int i=;i<=n;++i) {
        for(int j=;j<=po;++j) {
            if(!check(j,i))continue;
            for(int k=;k<=po;++k) {
                if(!check(k,i-)||(k&j)) continue;
                for(int p=;p<=po;++p) {
                    if(!check(p,i-)||(p&j)||(k&p)) continue;
                    dp[i&][k][j]=std::max(dp[i&][k][j],dp[(i&)^][p][k]+num[j]);
                }
                if(i==n)ans=std::max(ans,dp[n&][k][j]);
            }
        }
    }
    printf("%d\n",ans);
    return ;
}