首页 > 代码库 > poj3254Corn Fields状压Dp

poj3254Corn Fields状压Dp

用一个数记录上一行取的状态,在枚举此时的状态,并且把符合条件的传递下去。判断写的有点丑,roll 直接位运算搞定。

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;int dp[105][1<<13];int a[1000];int n,m;const int mod=100000000;int judge(int x,int state,int Map){   // printf("%d %d %d\n",x,state,Map);    int flag=0;    for(int i =0;i<m-1;i++){        int t=x&(1<<i);int t1=x&(1<<(i+1));        if(t&&t1) return 0; // 同行相邻不能重    }    for(int i=0;i<m;i++){        int t=x&(1<<i);int t1=Map&(1<<i);        if(t&&!t1)return 0;// 这点能取,原地图的这个位置也能取    }    for(int i=0;i<m;i++){        int t=x&(1<<i);int t1=state&(1<<i);        if(t&&t1) return 0;// 上点取了,这点就不能取了    }  //  system("pause");    return 1;}int dfs(int x,int state){    if(x==n) return dp[x][state]=1;    if(~dp[x][state]) return dp[x][state];    int gg=(1<<m);    int ans=0;    for(int i=0;i<gg;i++){        if(judge(i,state,a[x])){            ans+=dfs(x+1,i); ans%=mod;        }    }    return dp[x][state]= ans%mod;}int main(){    int t;    memset(dp,-1,sizeof(dp));   while(~ scanf("%d%d",&n,&m)){    memset(a,0,sizeof(a));    for(int i =0;i<n;i++)    for(int j=0;j<m;j++){        scanf("%d",&t);        if(t) a[i]|=(1<<j);//状压原地图。    }    cout<<dfs(0,0)%mod<<endl;   }    return 0;}