poj 3254 状压dp入门题

1、poj 3254  Corn Fields    状态压缩dp入门题

2、总结：二进制实在巧妙，以前从来没想过可以这样用。

题意：n行m列，1表示肥沃，0表示贫瘠，把牛放在肥沃处，要求所有牛不能相邻，求有多少种放法。

#include<iostream>

#include<cstring>

#include<cmath>

#include<queue>

#include<algorithm>

#include<cstdio>

#define max(a,b) a>b?a:b

using namespace std;

#define LL long long

#define INF 0x3f3f3f3f

const int mod=;

const int N=<<;

int m,n,num;

int mapn[],line[N];  //mapn存储每行状态，line枚举出所有每行本身不相邻的状态

int dp[][N];

int is1(int i)  //判断i本身二进制是否相邻

{

    return (i&(i>>));

}

int is2(int i,int j)  //判断i与j二进制是否相邻

{

    return (mapn[i]&line[j]);

}

void solve()

{

    memset(dp,,sizeof(dp));

    for(int i=;i<num;i++){

        if(!(is2(,i)))dp[][i]=;

    }

    for(int i=;i<=m;i++){

        for(int j=;j<num;j++){   //枚举第i行可能的情况

            if(is2(i,j))continue;   //剪枝

            for(int l=;l<num;l++){    //枚举i-1行可能的情况

                if(dp[i-][l]&&(!(line[j]&line[l]))){

                    dp[i][j]+=dp[i-][l];

                }

            }

        }

    }

    int sum=;

    for(int i=;i<num;i++){

        sum+=dp[m][i];

        sum%=mod;

    }

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

}

int main()

{

    while(scanf("%d%d",&m,&n)!=EOF)

    {

        memset(mapn,,sizeof(mapn));

        int a;

        for(int i=;i<=m;i++){

            for(int j=;j<n;j++){

                scanf("%d",&a);

                if(!a){

                    mapn[i]+=(<<j);   //存储下每行的状态，取a为0时才可比较

                }

            }

        }

        memset(line,,sizeof(line));

        num=;

        for(int i=;i<(<<n);i++){

            if(!is1(i))line[num++]=i;   //存储下所有本身二进制不相邻的数

        }

        solve();

    }

    return ;

}

poj 3254 状压dp入门题的相关教程结束。