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=100000000;
const int N=1<<13;

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

int is1(int i)  //判断i本身二进制是否相邻
{
    return (i&(i>>1));
}

int is2(int i,int j)  //判断i与j二进制是否相邻
{
    return (mapn[i]&line[j]);
}

void solve()
{
    memset(dp,0,sizeof(dp));
    for(int i=0;i<num;i++){
        if(!(is2(1,i)))dp[1][i]=1;
    }

    for(int i=2;i<=m;i++){
        for(int j=0;j<num;j++){   //枚举第i行可能的情况
            if(is2(i,j))continue;   //剪枝
            for(int l=0;l<num;l++){    //枚举i-1行可能的情况
                if(dp[i-1][l]&&(!(line[j]&line[l]))){
                    dp[i][j]+=dp[i-1][l];
                }
            }
        }
    }

    int sum=0;
    for(int i=0;i<num;i++){
        sum+=dp[m][i];
        sum%=mod;
    }
    printf("%d
",sum);
}

int main()
{
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        memset(mapn,0,sizeof(mapn));
        int a;
        for(int i=1;i<=m;i++){
            for(int j=0;j<n;j++){
                scanf("%d",&a);
                if(!a){
                    mapn[i]+=(1<<j);   //存储下每行的状态，取a为0时才可比较
                }
            }
        }

        memset(line,0,sizeof(line));
        num=0;
        for(int i=0;i<(1<<n);i++){
            if(!is1(i))line[num++]=i;   //存储下所有本身二进制不相邻的数
        }

        solve();
    }

    return 0;
}