首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。