首页 > 代码库 > POJ 2411 状压dp
POJ 2411 状压dp
题目大意：
用 1*2 或者2 *1的木板填满 h*w的长方形，问总共有多少种填充方法
直接dfs会超时，因为后面答案甚至爆了int，直接搜，肯定也是long long 的时间复杂度
这里我们将当前位置没放置任何木板为 0 ， 如有放置则看为 1
每次通过当前行 i 的状态 old 找到下一行 i + 1 所有满足当前行状态的状态 new ， 将 dp[i+1][new] += dp[i][old]
这个new的状态一定会在old状态为 0 的位置为1 ， 因为上一行为 0 ， 说明是留给竖木板的， 那么新一行的对应位置必然放了竖直木板
总状态为cnt ， 那么至少要保证 new 状态中 包含了 ~old&cnt 这个状态中的所有1
但是我们要找到所有可以对应old状态的new状态，那么就dfs搜可以在转换状态后加横木板的所有情况即可
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 6 int h,w,cnt; 7 long long ans,add; 8 long long dp[12][1<<12]; 9 10 void dfs(int k , int state , int i)11 {12 if(k > w){13 dp[i+1][state] += add; //所有包含一开始传入状态的放置横木板后的状态14 return;15 }16 if(k+1 <= w && !(state & (1<<k)) && !(state & (1<<k-1))){17 dfs(k+2 , state | (1<<k-1) | (1<<k) , i);18 }19 dfs(k+1 , state , i);20 }21 22 int main()23 {24 25 // freopen("test.in","rb",stdin);26 while(scanf("%d%d",&h,&w)!=EOF){27 if(h == 0 && w == 0) break;28 if((h&1) && (w&1)){29 puts("0");30 continue;31 }32 cnt = (1<<w)-1;33 memset(dp,0,sizeof(dp));34 add = 1;35 dfs(1,0,0);36 for(int i=1 ; i<h ; i++){37 for(int j=0;j<=cnt;j++)38 if(dp[i][j])39 {40 add = dp[i][j];41 //传入的state是必须要放置的位置，根据dfs来找到那些包含state状态的且能放一个横木板的状态42 dfs(1 , ~j&cnt , i);//这里本来取~j就够了，但是有64位，那么最前面为0 的位置取反后也为1，那么~j得到的其实是个负数，所以还要进行&操作43 44 }45 }46 printf("%I64d\n",dp[h][cnt]);47 }48 return 0;49 }
POJ 2411 状压dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。