首页 > 代码库 > poj3254（状压dp）
poj3254（状压dp）
题目连接：http://poj.org/problem?id=3254
题意：一个矩阵里有很多格子，每个格子有两种状态，可以放牧和不可以放牧，可以放牧用1表示，否则用0表示，在这块牧场放牛，要求两个相邻的方格不能同时放牛，即牛与牛不能相邻。问有多少种放牛方案(一头牛都不放也是一种方案)
分析：dp[i][state]表示状态为state，到达i行时符合条件的总方案数，则dp[i][state]=sigma(dp[i-1][state‘])state‘为符合条件的状态。
#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-9#define N 100010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int dp[15][600],n,m,tot;int cur[15],state[600];void init()//预处理出每行所有符合条件的状态{ int sum=1<<m; tot=0; for(int i=0;i<sum;i++) { if(!(i&(i<<1)))state[++tot]=i; }}bool ok(int state,int k)//判断状态state在k行时是否符合条件{ if(state&cur[k])return 0; return 1;}int main(){ while(scanf("%d%d",&n,&m)>0) { init(); for(int i=1;i<=n;i++) { cur[i]=0; for(int j=1;j<=m;j++) { int x; scanf("%d",&x); if(!x)cur[i]+=1<<(m-j);//记录每行不能放牛的状态 } } FILL(dp,0); for(int i=1;i<=tot;i++) { if(ok(state[i],1))dp[1][i]=1; } for(int i=2;i<=n;i++) { for(int j=1;j<=tot;j++) { if(!ok(state[j],i))continue; for(int k=1;k<=tot;k++) { if(!ok(state[k],i-1))continue; if(state[j]&state[k])continue; dp[i][j]+=dp[i-1][k]; dp[i][j]%=mod; } } } int ans=0; for(int i=1;i<=tot;i++) ans=(ans+dp[n][i])%mod; printf("%d\n",ans); }}
poj3254（状压dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。