POJ 3254 狀壓DP，poj3254壓dp

POJ 3254 狀壓DP，poj3254壓dp

題目大意： 一個農民有一片n行m列 的農場   n和m 范圍[1,12]  對於每一塊土地 ，1代表可以種地，0代表不能種。 因為農夫要種草喂牛，牛吃草不能挨著，所以農夫種菜的每一塊都不能有公共邊。 告訴你 n ，m 和那些地方能種菜哪些地方不能種菜，求農夫一共有多少種方案種菜

解法：

基本思想是狀壓 也就是用一個int 型的數代表一行的種菜策略，二進制的0代表該位不能種菜，1位代表能種菜，使用位運算使處理速度變快

對於單行行，最多有2^12 種情況，並且 2^12種情況裡面還有很多不滿足題意的  篩選一下每行最多有400左右種情況，

1 先篩選出每行滿足題意的情況 

2 如何判斷兩行能否相鄰？ 如果一行狀壓的數使 i 另一行狀壓的數是 j  如果 i|j ==i+j 說明兩行可以相鄰

3  如何判斷一個種法能否滿足某一行的要求？  

以樣例來看

2 3

1 1 1

0 1 0

第一行二進制是7 第二行二進制是2 

如果一個種菜的決策時 i  如果 i|2==2 就說明他能滿足第二行的要求，，

然後就是dp[i][k] 代表第i行像k這樣種菜的情況數

然後就是渣渣參考代碼  g++  

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <string>
#include <queue>
#include <cstring>
#define CL(a,b) memset(a,b,sizeof(a))
#define ll __int64
#define TEST cout<<"TEST   ***"<<endl;
#define INF 0x7fffffff
#define MOD 100000000
using namespace std;

ll dp[15][1000];
int inn[4100],m,n;
int num[12];

int initinn()
{
    int i,j,preinn,nowinn,taginn;
    CL(inn,0);
    for(i=0;i<4100;i++)
    {
        preinn=0,taginn=1;
        j=i;
        while(j)
        {
            nowinn=j&1;
            if(nowinn==1&&preinn==1)
            {
                taginn=0;
                break;
            }
            preinn=nowinn;
            j/=2;
        }
        inn[i]=taginn;
    }
    i=0;j=0;
    while(j<4100)
    {
        if(inn[j]==1)
        {
            inn[i++]=j;
        }
        j++;
    }
    return i;
}

using namespace std;

int main()
{
    initinn();
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        int i,j,k,ma=(1<<m)-1;
        int a,sum;
        CL(dp,0);
        for(i=1;i<=n;i++)
        {
            sum=0;
            for(j=0;j<m;j++)
            {
                scanf("%d",&a);
                sum*=2;
                sum+=a;
            }
            num[i]=sum;
        }
        dp[0][0]=1;
        for(i=1;i<=n;i++)
        {
            for(j=0;inn[j]<=ma;j++)
            {
                if((inn[j]|num[i])!=num[i])continue;
                for(k=0;inn[k]<=ma;k++)
                {
                    if((inn[j]|inn[k])==inn[j]+inn[k])
                    {
                        dp[i][j]+=dp[i-1][k];
                        dp[i][j]%=MOD;
                    }
                }
            }
        }
        ll rem=0;
        for(i=0;inn[i]<=ma;i++)
        {
            rem+=dp[n][i];
        }
        rem%=MOD;
        printf("%I64d\n",rem);
    }
    return 0;
}