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 ;

}