POJ 2411 (动态规划-状压DP AND 轮廓线DP)

悠悠 2022-05-29 00:29 245阅读 0赞

问题描述:

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.

![91cd2a849209448a71d50fa577e5d5ed_v_1520837903][]  
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!

Input

The 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.

Output

For 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 2
    1 3
    1 4
    2 2
    2 3
    2 4
    2 11
    4 11
    0 0

Sample Output

1
    0
    1
    2
    3
    5
    144
    51205

题目题意:给我们一个h\*w的矩形，我们用1\*2的矩形去覆盖，覆盖种数

状压DP：对于每一行我们用01二进制表示其状态1表示横放或者竖放的下面一块，0表示竖放的上面一块。

则上一行为0的地方这一行必须为1，其他的任意，还有一点上下俩行想与必须满足每一个连续的1区间的长度是偶数

很简单，只有上下为1才有是相与为1，那么都是横放，砖的长度为2偶数

代码如下:

#include<iostream>
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #define ll long long
    using namespace std;
    
    ll dp[2][1<<12];
    bool vis[1<<12];
    int h,w;
    
    bool check(int s)
    {
       int cnt = 0;
        while(s){
          if(s&1){
            cnt++;
          }
          else{
            if(cnt&1)return false;
              cnt = 0;
            }
            s>>=1;
        }
        if(cnt&1)return false;
        return true;
    }
    void init()
    {
        memset (vis,false,sizeof (vis));
        for (int i=0;i<=(1<<11);i++){
            if (check(i)) vis[i]=true;
        }
    }
    int main()
    {
        init();
        while (scanf("%d%d",&h,&w)!=EOF) {
            if (h==0&&w==0) break;
            memset (dp,0,sizeof (dp));
            for (int i=0;i<(1<<w);i++) {//状态可以先处理出来
                if (vis[i]) dp[0][i]=1;
            }
            for (int i=1;i<h;i++) {
                int next=i%2;
                int fa=1-next;
                memset (dp[next],0,sizeof (dp[next]));
                for (int j=0;j<(1<<w);j++){
                    for (int k=0;k<(1<<w);k++) {
                        if (dp[fa][k]==0) continue;
                        int cnt=((1<<w)-1)^k;//这个地方比较巧妙，想想
                        if ((cnt&j)!=cnt) continue;
                        if (vis[j&k]) dp[next][j]+=dp[fa][k];
                    }
                }
            }
            printf("%lld\n",dp[(h-1)%2][(1<<w)-1]);
        }
        return 0;
    }

轮廓线DP

先看一下大佬博客[点击打开链接][Link 1]

从一个轮廓线转移到另一轮廓线要保证处理的当前结点的上方一定要被覆盖

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    using namespace std;
    const double PI=acos(-1);
    const int MAX=1e6+100;
    const int MOD=1e9+7;
    typedef long long ll;
    ll d[2][1<<12];
    int main()
    {
        int n,m;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            if(n==0&&m==0)break;
            memset(d,0,sizeof d);
            int pre=0,now=1;
            d[pre][(1<<m)-1]=1;
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    for(int k=0;k<(1<<m);k++)
                    {
                        if(d[pre][k]==0)continue;
                        if((k<<1)&(1<<m))d[now][(k<<1)%(1<<m)]+=d[pre][k];//上面已经有了，不放
                        if((k&(1<<(m-1)))==0&&i)d[now][(k<<1)^1]+=d[pre][k];//竖放
                        if(j&&(k&1)==0&&(k&(1<<(m-1))))d[now][((k<<1)^3)%(1<<m)]+=d[pre][k];//横放而且保证当前结点的上方一定要被覆盖了
                    }
                    memset(d[pre],0,sizeof d[pre]);
                    now^=1;
                    pre^=1;
                }
            }
            cout<<d[pre][(1<<m)-1]<<endl;
        }
        return 0;
    }

[91cd2a849209448a71d50fa577e5d5ed_v_1520837903]: https://odzkskevi.qnssl.com/91cd2a849209448a71d50fa577e5d5ed?v=1520837903
[Link 1]: http://blog.csdn.net/u013480600/article/details/19499899