poj3254状压DP入门

G - 状压dp

Crawling in process... Crawling failed Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u

Submit Status

Description

Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can't be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.

Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.

Input

Line 1: Two space-separated integers: M and N
Lines 2.. M+1: Line i+1 describes row i of the pasture with N space-separated integers indicating whether a square is fertile (1 for fertile, 0 for infertile)

Output

Line 1: One integer: the number of ways that FJ can choose the squares modulo 100,000,000.

Sample Input

2 3
1 1 1
0 1 0

Sample Output

Hint

Number the squares as follows:

1 2 3
  4

There are four ways to plant only on one squares (1, 2, 3, or 4), three ways to plant on two squares (13, 14, or 34), 1 way to plant on three squares (134), and one way to plant on no squares. 4+3+1+1=9.

解析见代码：

tips:位运算优先级极其诡异，在使用位运算的时候最好要加上括号

总结下本题用到的几种位运算：

1.判断一个数的二进制位是否有两个相邻的1 x&(x<<1)==0

2.取一个数的第k位 p&(1<<(k-1))

3.判断两个数是不是同一位有1 a&b==0?

/*
  poj3254
  分类：状压DP
  因为后一行的状态只与前一行有关，考虑使用DP做
  每一行最多有12个格子，用0表示不取，1表示取总共有1<<12-1种情况
  首先单独看某一行，合法的状态是没有两个1彼此相邻，用位运算来判断
  i&(i<<1)为0则表示没有相邻的1，是合法状态。
  先初始化出所有的不考虑某块地不能选择的情况，保存所有的合法状态，
  然后再结合题目进行筛选，筛选范围时1~(1<<m),看那种合法状态是否
  与草原实际相符，具体办法就是依次取合法状态的某一位，如果改位为
  1但实际上这块草地不能取，这种状态就是不可行的，第一行若第j种状态可行
  dp[i][j]=1，状态转移方程则是dp[i][j]+=dp[i-1][k],k代表上一层的可行状态
  若不可行，dp[i-1][k]=0,所以初始化时要将dp数组初始化为0
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=(1<<12);//最多有12列
int v[maxn],dp[13][maxn];
int a[15][15];//用来存图；
int n,m;
const long long mod=100000000;
int tot;
void init()
{
    tot=0;
    for(int i=0;i<maxn;i++)//记录所有合法状态
    {
        if((i&(i<<1))==0)
            v[tot++]=i;
    }
}
bool check(int row,int p)
{
    for(int i=1;i<=m;i++)
    {
        if((p&(1<<(i-1)))&&!a[row][i])//这种状态不符合实际
         return true;
    }
    return false;
}
int main()
{
    init();
   // for(int i=0;i<tot;i++)
     //   cout<<v[i]<<" ";
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
        for(int i=1;i<=n;i++)
        {
            for(int j=0;v[j]<(1<<m);j++)
            {
                if(check(i,v[j])) continue;
                if(i==1)
                {
                    dp[i][j]=1;
                    continue;
                }
                for(int k=0;v[k]<(1<<m);k++)
                {
                    if((v[j]&v[k])==0)
                        dp[i][j]+=dp[i-1][k];
                }
            }
        }
        __int64 ans=0;
        for(int i=0;v[i]<(1<<m);i++)
        {
            ans=(ans+dp[n][i])%mod;
        }
        printf("%I64d
",ans);
    }
}