4.5算法之动态规划 1413:Mondriaan’s Dream

http://noi.openjudge.cn/ch0405/1413/

题目

描述
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!
输入
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.
输出
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.

思路

基于一下两个思路
0表示下一层对应位置必须为1,即竖向砖块的第一块砖,1表示下一层可为0可为1,无影响
dp思路
dp[i][status] = sum(dp[i-1][k]) k in [0,2^w-1]
其中 sum 求和时要对 status 和 k 进行校验
– status|k == 2^w-1,及保证竖向不会出现连续的两个0这种非法情况
– status&k 要保证所有出现的 1 都为连续的2 个 1,否则意味着出现了单格的错位,010的下层必定为101,则在最低端无法满足全1的要求与操作取到的1为横放的块(1有两种含义),只要保证横放的块都符合规则即可。

源码

//
//  1413.cpp
//  test
//
//  Created by bytedance on 2020/7/29.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <vector>
#include <iostream>

using namespace std;
long long w,h;

//bool check(long long x){
//
//}
vector<vector<long long>> dp;
bool check(long long x){
    for(long long i = 0;i < w;++i){
        if((x&(1<<i))!=0){
            if((x&(1<<(i+1)))!=0){
                ++i;
            }else{
                return false;
            }
        }
    }
    return true;
}
int main(){

    while(cin >> h >> w){
        if(h==0&&w==0)break;
        if(h*w%2==1){
            cout<<0<<endl;
            continue;
        }
        long long statusNum = 1<<w;
        dp.clear();
        dp.resize(h+1,vector<long long>(1<<w,0));
        for(long long i = 0;i < statusNum;++i){
            if(check(i))
                dp[1][i]=1;
        }
        for(long long i = 2;i <= h;++i){
            for(long long now = 0;now < statusNum; ++now){
                for(long long up = 0;up < statusNum;++up){
                    if((now|up)==statusNum-1){
                        if(check(now&up))
                            dp[i][now]+=dp[i-1][up];
                    }
                }
            }
        }
        cout << dp[h][statusNum-1]<<endl;
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注