poj2411_状压dp-白红宇

poj2411_状压dp

阅读量：4947 次

发布时间：2019-06-11

本文共 1551 字，大约阅读时间需要 5 分钟。

题目链接：

题目描述：用1*2 的矩形通过组合拼成大矩形，求拼成指定的大矩形有几种拼法。

首先我们先求用1*2 的矩形拼成 n*m的矩形有多少种拼法

当n*m为奇数时，一定是不会拼出来的，因为想要拼出来就需要整数倍的小矩形数目。

分两个步骤：1）先求出相邻两行的转化关系

2）通过相邻两行的转化关系算出经过n次转化有几种方法能拼成n*m的矩阵

1）状态标记横放和竖放的下一个均为1，竖放的上一个和不放置为0 ，每行可以转化为1个2进制数。当这一行访问结束时，就会得到上一行状态，和该行状态，因为所有情况都是我们设置的，所以pre状态一定会转化为now状态

对于每一个位置，我们有三种放置方法：1. 竖直放置2. 水平放置3. 不放置

d为当前列号，初始化d, now, pre都为0。now为当前行，pre为当前行的上一行

1. d = d + 1, now << 1 | 1, pre << 1; // 竖直放置，当前行该列为1，上一行该列置为为0

2. d = d + 2, now << 2 | 3, pre<< 2 | 3; // 横放都为11

3. d = d + 1, now << 1, pre<< 1 | 1; // 上一行该列置为1，不能竖放，不放置的状态

因为转移状态有很多种，所以用dfs去枚举各种可行的状态。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
             9 #include 
             
              10 #include 
              
               11 #define INF 0x3f3f3f3f12 using namespace std;13 14 typedef long long LL;15 int h, w, cont;16 LL dp[12][1 << 11];17 int path[(1 << 11)*11][2];18 void dfs(int col, int now, int pre)19 {20 if(col > w)21 return;22 if(col == w)23 {24 path[cont][0] = pre;25 path[cont++][1] = now;26 return;27 }28 dfs(col+2, (now<<2)|3, (pre<<2)|3);29 dfs(col+1, (now<<1)|1, pre<<1);30 dfs(col+1, now<<1, (pre<<1)|1);31 }32 int main()33 {34 while(~scanf("%d %d", &h, &w) && h + w)35 {36 cont = 0;37 dfs(0, 0, 0);38 memset(dp, 0, sizeof(dp));39 dp[0][(1 << w) - 1] = 1;40 for(int i = 0; i < h; i++)41 {42 for(int j = 0; j < cont; j++)43 dp[i + 1][path[j][1]] += dp[i][path[j][0]];44 }45 printf("%lld\n", dp[h][(1<

转载于:https://www.cnblogs.com/luomi/p/5687657.html

你可能感兴趣的文章