SGU131 Hardwood floor

SGU131 Hardwood floor
제목 의 대의
N * M 의 행렬 이 있 습 니 다. 1 * 2 의 사각형 과 2 * 2 의 L 형 으로 겹 치지 않 고 누락 없 이 덮어 쓰 고 몇 가지 방안 이 있 는 지 물 어보 세 요.
알고리즘 사고
상 압 DP, f[j][S] 은 앞의 j - 1 열 을 채 우 고 j 열의 상태 가 S 인 방안 수 는 1 열 에 대해 1 * 2 의 사각형 으로 덮어 쓸 수 있 는 지 직접 판단 하고 경계 조건 으로 j 열 에 대해 보조 상태 g[S] 를 계산 하여 j - 1 열과 j 열의 상태 가 S 인 방안 수 를 나타 낸다.

S 가 j - 1 열 에 불과 하 다 면 g[S] = f[j-1][S]

그렇지 않 으 면 j 열 맨 위 에 있 는 칸 을 찾 아 두 가지 모양 의 6 개 상태 로 덮어 보 려 고 합 니 다. g[S] = sigma{g[S-Si]}， Si in S

마지막 으로 f[j][S] 는 g[S] 에서 j - 1 열 이 채 워 진 상태 에 대응 합 니 다.
시간 복잡 도: O (M×22N)
코드

/** * Copyright © 2015 Authors. All rights reserved. * * FileName: 131.cpp * Author: Beiyu Li <[email protected]> * Date: 2015-06-13 */
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)

typedef long long LL;
typedef pair<int, int> Pii;

const int inf = 0x3f3f3f3f;
const LL infLL = 0x3f3f3f3f3f3f3f3fLL;

int n, m;
LL f[2][1<<9], g[1<<18];
int sp[6][2] = {{0, 3}, {1, 1}, {1, 3}, {2, 3}, {3, 1}, {3, 2}}, s[6];

LL solve()
{
        if (n > m) swap(n, m);
        if (n == 1) return ~m & 1;
        rep(k,6) s[k] = sp[k][1] << n | sp[k][0];
        int o = 0, half = (1 << n) - 1;
        For(S,0,half) {
                f[o][S] = 1;
                rep(i,n) if ((1 << i) & S) {
                        int k = i + 1;
                        while (k < n && ((1 << k) & S)) ++k;
                        if ((k - i) & 1) { f[o][S] = 0; break; }
                        i = k - 1;
                }
        }
        For(j,1,m-1) {
                o ^= 1;
                rep(S,1<<(n*2)) {
                        if (S <= half) { g[S] = f[o^1][S]; continue; }
                        g[S] = 0;
                        rep(i,n) if ((1 << (i + n)) & S) {
                                rep(k,6) if (k < 5 || i) {
                                        int S0 = s[k] << (k < 5? i: i - 1);
                                        if ((S0 & S) == S0) g[S] += g[S^S0];
                                }
                                break;
                        }
                }
                rep(S,1<<n) f[o][S] = g[S<<n|half];
        }
        return f[o][(1<<n)-1];
}

int main()
{
        scanf("%d%d", &n, &m);
        printf("%lld
", solve());

        return 0;
}