首页 > 代码库 > poj2411（状压dp）
poj2411（状压dp）
题目链接：http://poj.org/problem?id=2411
题意：由1*2 的矩形通过组合拼成大矩形，求拼成指定的大矩形有几种拼法。
分析：如果是横着的就定义11，如果竖着的定义为竖着的01，状态兼容时只需考虑两种情况，当前行&上一行，是不是全为1，不是说明竖着有空（不可能出现竖着的00），另一个要检查当前行里有没有横放的，但为奇数的连续1。
#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;LL dp[15][1<<12];int fit[1<<12];int tot,n,m;bool ok(int x)//判断一行状态中是否有奇数的连续1{ int opp=0; while(x) { if(x&1)opp++; else { if(opp&1)return 0; opp=0; } x>>=1; } return (opp&1)==0;}bool judge(int j,int k){ if((j|k)!=(1<<m)-1)return false; return fit[j&k];}int main(){ for(int i=0;i<(1<<11);i++)if(ok(i))fit[i]=1; while(scanf("%d%d",&n,&m)>0) { if(n+m==0)break; FILL(dp,0); if(m*n&1) { puts("0");continue; } if(n<m)swap(n,m); for(int i=0;i<(1<<m);i++) dp[1][i]=fit[i]; for(int i=2;i<=n;i++) { for(int j=0;j<(1<<m);j++) for(int k=0;k<(1<<m);k++) if(judge(j,k)) dp[i][j]+=dp[i-1][k]; } printf("%lld\n",dp[n][(1<<m)-1]); }}
poj2411（状压dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。