首页 > 代码库 > POJ2411 状态压缩

POJ2411 状态压缩

2024-07-10 21:44:46   216人阅读

Mondriaan‘s DreamTime Limit: 3000MS        Memory Limit: 65536KTotal Submissions: 11208        Accepted: 6521Description
Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his ‘toilet series‘ (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways. 

  

                                                                                              
Expert as he was in this material, he saw at a glance that he‘ll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won‘t turn into a nightmare!InputThe input contains several test cases. Each test case is made up of two integer numbers: the height h and the width w of the large rectangle. Input is terminated by h=w=0. Otherwise, 1<=h,w<=11.OutputFor each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.Sample Input
1 21 31 42 22 32 42 114 110 0Sample Output10123514451205

 

                                                                                                                       0

经典状压，1*2的瓷片只有两种状态：1、横着贴    2、竖着贴。    横着贴表示为 1 1 ，竖着贴表示为1  ，那么贴完瓷片后整个墙被0和1两个数字覆盖，即每一行都是0和1，那么每一行可以用二进制数字表示，然后问题就成为上面一行的数字推出下面一行数字的问题。

怎么推呢，假设第i行第j个位置（用map[i][j]表示）为0，那么map[i+1][j]只能有一个状态即瓷片竖着贴，map[i+1][j]=1;

若map[i][j]=1,那么map[i+1][j]这个位置可以竖着贴，即map[i+1][j]=0是可以成立的。   那么map[i+1][j]可以横着贴吗？当然可以，不过要取决于map[i][j+1]位置的状态，若map[i][j+1]=0,那么map[i+1][j]只能竖着贴，若map[i][j+1]=1,那么map[i+1][j]=map[i+1][j+1]是可以成立的。

 

由这几个状态转化可以从上一行二进制数，把下一行二进制数推出。

 

代码：

 1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <iostream> 5 using namespace std; 6  7 int n, m; 8 int used[12]; 9 __int64 dp[12][2048];10 11 12 void dfs(int p,int q,int sum,int i)   13 {14     if(i>=m)                                     //第i+1行每一列已求出 15     {16         dp[p+1][sum]+=dp[p][q];17         return;18     }19     if(used[i])                            //如果此处为0，那么下一行此处必为1 20     dfs(p,q,sum,i+1);21     else{22         int num1=1<<i;23         int num2=1<<(i+1);24         dfs(p,q,sum,i+1);                 //此处为1，下一行竖着贴 25         if(!used[i+1])26             dfs(p,q,sum+num1+num2,i+2);    //此处为1，下一行横着贴 27     }28 }29 30 void flag(int p,int q)               //找出第i行二进制位为0的位置，并dfs 31 {32     int x;33     int sum=0, i;34     memset(used,0,sizeof(used));35     used[m]=0;36     for(i=0;i<m;i++)37     {38         x=1<<i;39         if((x&q)==0) {40             used[i]=1;41             sum+=x;42         }    43     }44     dfs(p,q,sum,0);45 }46 main()47 {48     while(scanf("%d %d",&n,&m)==2)49     {50         if(n==0&&m==0) break;51         memset(dp,0,sizeof(dp));52         if(n<m)53         swap(n,m);54         dp[0][(1<<m)-1]=1;55         for(int i=0;i<n;i++)56         {57             for(int j=0;j<(1<<m);j++)58             {59                 if(!dp[i][j]) continue;               //当第i行二进制为j 该状态不成立的话跳过继续以另一个二进制循环，否则推出下一行二进制 60                 flag(i,j);61             }62         }63         printf("%I64d\n",dp[n][(1<<m)-1]);    //易知，最后一行所有位置的二进制都为1 64     }65 }

 

 

 

                                                                                                                               


联系
我们