首页 > 代码库 > poj2411(状态转移,dfs搜索转移)
poj2411(状态转移,dfs搜索转移)
题目链接
题意:用1*2的小矩形拼成n*m(n,m<=11)的矩阵有多少种方案。
解法:状态压缩,dfs求转移。当前一列的状态确定后,后一列必须用横向的矩形来填补前一列的空白格,所以前一列不为空时,这一列可以选择也为空让下一列来填补,或是本列来个纵向的矩形填补(如果有连续的两个空格的话)。
代码:
/****************************************************** * @author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <string.h> //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=100010; const LL INF=0x3FFFFFFF; LL dp[2][(1<<12)]; int n,m; void dfs(int now,int wei,int st,LL num) { if(wei==m) { dp[now][st]+=num; return ; } dfs(now,wei+1,st,num); if(wei<m-1&&!(st&(1<<wei))&&!(st&(1<<(wei+1)))) dfs(now,wei+2,st|(1<<wei)|(1<<(wei+1)),num); } int main() { while(cin>>n>>m&&n+m) { int now=0; memset(dp,0,sizeof dp); dfs(now,0,0,1); for(int i=1; i<n; i++) { memset(dp[now^1],0,sizeof dp[now]); for(int j=0; j<(1<<m); j++) if(dp[now][j]) dfs(now^1,0,(~j)&((1<<m)-1),dp[now][j]); now^=1; } printf("%I64d\n",dp[now][(1<<m)-1]); } return 0; } /* n*1+((n-1)/2+(n-2)/3)*/
poj2411(状态转移,dfs搜索转移)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。