Skip to content

11383: 【原1383】畅畅的牙签袋

题目

题目描述

author: SamJia 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1383

题目描述

畅畅说:“你们都说窝脑子瓦特了,我看你们才是脑子瓦特嘞- -”

为了阻挠我们再次揭露他的无chǐ,畅畅妄图破坏我们的显示器,他拿出了自己收集的牙签包装袋,其大小是1×2的矩形,他想用密铺的方式把显示器全部遮挡住。显示器大小是W×H的矩形,畅畅把包装袋背面涂上了胶水,开始一块一块粘到显示器上,要求不能有包装袋重叠,也不能有显示器的某一部分没被遮挡,包装袋的放置只有两种情况:横放和竖放。

畅畅为自己的周密计划洋洋得意之时,脑子又瓦特了,他想让你帮他算算针对每台显示器一共有多少种不同的密铺方式。

说明

  1. 认为显示器是有方向的,即对称的密铺方式要算重复计数,例如 2×2 的显示器密铺方案有两种,一种是2个包装袋都横放,另一种是两个包装袋都竖放。

  2. 不能密铺的则输出0。

  3. 牙签包装袋足够用。

输入格式

输入包括若干行,每行有两个整数Wi和Hi,表示这台显示器大小,输入数据以Wi=Hi=0作为结束,每台显示器大小 1<=Hi,Wi<=11。

输出格式

针对每行输入,每次输出一个整数表示对该显示器密铺的方案总数。Wi=Hi=0时不需要输出。

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

提示

畅畅说如果Wi×Hi是奇数的话可行的方案数就是0了。

畅畅思来想去,认为以行为单位来一行行填充,同时用状态压缩的方式表示每一行的填充状态,0表示空1表示已填充,如一个长为3的行有000,001,010,011,100,101,110,111这样几种状态表示。

畅畅觉得动态规划太难的话,只有暴力搜索了。

畅畅说30%测试点只有一台显示器,70%测试点只有不超过十台显示器,100%测试点只有不超过121台显示器

畅畅说答案很小的,long long就够了

yyong119's solution

#include <iostream>
#include <cstring>
using namespace std;

int W, H;
long long cnt = 1;
long long dp[12][1 << 12];

void findall(int line, int state, int pos) {

    if (pos == W) {
        dp[line][state] += cnt;
        return;
    }
    findall(line, state, pos + 1);//Leave this position empty
    if (pos <= W - 2 && !(state & (1 << pos)) && !(state & (1 << (pos + 1)))) {//Fill two horizontal positions
        int next = state | (1 << pos) | (1 << (pos + 1));
        findall(line, next, pos + 2);
    }
}

int main() {

    while (cin >> W >> H && W != 0) {

        if (W > H) { int tmp = W; W = H; H = tmp; }
        if (W * H % 2 == 1) {
            cout << 0 << endl; continue;
        }
        memset(dp, 0, sizeof(dp));
        cnt = 1;

        findall(1, 0, 0);
        for (int i = 2; i <= H; ++i)
            for (int j = 0; j < (1 << W); ++j) {
                if (dp[i - 1][j]) cnt = dp[i - 1][j];
                    else continue;
                findall(i, (~j) & ((1 << W) - 1), 0);
            }

        cout << dp[H][((1 << W) - 1)] << endl;
    }
    return 0;
}