hdu 1400 Mondriaan's Dream

本文主要是介绍hdu 1400 Mondriaan's Dream，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

hdu 1400  Mondriaan's Dream

poj上有跟这题类似的题目，状态压缩dp， 应为方块的形状为1*2 ，所以每行的放置情况最多和上层的放置情况有关，dp[ i ] [ j ] 表示在第i层放置情况为j的方法数，j中1代表放0不放

#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cstdio>using namespace std;long long dp[11][1<<11];
int h,w;void init(int state,int id)
{if(id>=w) { dp[0][state]++;return; }init(state<<1,id+1);if(id+2<=w) init(state<<2|3,id+2); //  放
}
void dfs(int r,int id,int pre,int now)
{if(id>=w){dp[r][now]+=dp[r-1][pre];return;}dfs(r,id+1,pre<<1|1,now<<1);   // 不放if(id+1<w) dfs(r,id+2,pre<<2|3,now<<2|3); // 横放dfs(r,id+1,pre<<1,now<<1|1);  // 竖放
}
int main()
{while(scanf("%d%d",&h,&w)==2,(h||w)){if((h*w)%2){printf("0\n");continue;}memset(dp,0,sizeof(dp));init(0,0);// for(int i=0;i<(1<<w);i++)//   cout<<i<<" dd "<<dp[0][i]<<endl;for(int i=1;i<h;i++)dfs(i,0,0,0);printf("%I64d\n",dp[h-1][(1<<w)-1]);}return 0;
}

这篇关于hdu 1400 Mondriaan's Dream的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---