睡前小dp-poj3254-状压dp入门

从这里学的 http://blog.csdn.net/accry/article/details/6607703

状压dp的入门题。一片N×M的田地，有的地方可以种玉米，有的地方不可以。种玉米的区块不能相邻。种玉米的求总方案数，不种玉米也是一种方案。

每一行总共2^N种状态，其中删去有相邻的状态，删除不符合给定条件的状态。保留下最终的所有状态。然后开始dp。

从上往下，每一行之依赖于上一行。所以从上一行转移过去，把状态数加起来就行了。

其中几个函数写的比较精妙，结合二进制运算理解一下并不难。

/*--------------------------------------------------------------------------------------*/

//        Helica's header

//        Second Editions

//        2015.11.7

//

#include <algorithm>

#include <iostream>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cstdio>

#include <vector>

#include <string>

#include <queue>

#include <stack>

#include <cmath>

#include <set>

#include <map>

//debug function for a N*M array

#define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++)\

{for(int j=;j<(M);j++){\

printf("%d",G[i][j]);}printf("\n");}

//debug function for int,float,double,etc.

#define debug_var(X) cout<<#X"="<<X<<endl;

/*--------------------------------------------------------------------------------------*/

using namespace std;

const int MOD = ;

int N,M,T;

int dp[][],state[],cur[];

int cnt;

bool ok(int x)

{

    if(x&(x<<)) return ;

    return ;

}

bool fit(int s,int c)

{

    if(s&c) return ;

    return ;

}

int main()

{

    while(~scanf("%d%d",&N,&M))

    {

        for(int i=;i<=N;i++)

        {

            cur[i] = ;

            for(int j=;j<=M;j++)

            {

                int a;

                scanf("%d",&a);

                if(a==) cur[i] += (<<(M-j));

            }

        }

        cnt=;

        for(int i=;i < <<M;i++) if(ok(i))

        {

            state[++cnt] = i;

        }

        memset(dp,,sizeof dp);

        for(int i=;i<=cnt;i++) if(fit(state[i],cur[]))

            dp[][i] = ;

        for(int i=;i<=N;i++)

        {

            for(int j=;j<=cnt;j++)

            {

                if(!fit(state[j],cur[i])) continue;

                for(int k=;k<=cnt;k++)

                {

                    if(!fit(state[k],cur[i-])) continue;

                    if(state[j]&state[k]) continue;

                    dp[i][j] = (dp[i][j]+dp[i-][k])%MOD;

                }

            }

        }

        int ans = ;

        for(int i=;i<=cnt;i++) ans = (ans+dp[N][i])%MOD;

        printf("%d\n",ans);

    }

}