轮廓线 DP 入门

发表于2021-04-02更新于2023-09-17字数统计1.7k阅读时长17分作者Shane

A Hanjo

题目链接

Description

求用 AA 个 2∗12*1，BB 个 1∗11*1 的方块填满 H∗WH*W 的方格的方案数。

Solution

见博客 AtCoder Beginner Contest 196。

B Tiling Dominoes

题目链接

Desciption

求用 2∗12*1 的方块填满 H∗WH*W 的方格的方案数。

Solution

上一题的弱化版本。由于方块数目没有限制，故只需要设 dp[i][s]dp[i][s] 表示考虑前 ii 个方格，从这个方格开始前 WW 个方格填充状态为 ss，除了这些方格外其余方格全部被填满的方案数。现在考虑第 i+1i+1 个方格，根据 s′s'，sus_u 和 sls_l（和上一题题解中的定义一致），有如下转移：

  • su=0s_u = 0，则必须竖着放一个 2∗12*1 的方块，于是有：

dp[i+1][s′∣1][a+1][b]←dp[i][s][a][b]dp[i+1][s'|1][a+1][b] \leftarrow dp[i][s][a][b]

  • slsu=01s_l s_u = 01，则可以横着放一个 2∗12*1 的方块，或者不放，从而：

dp[i+1][s′∣3][a+1][b]←dp[i][s][a][b]dp[i+1][s′][a][b]←dp[i][s][a][b]\begin{aligned} dp[i+1][s'|3][a+1][b] \leftarrow dp[i][s][a][b] \\ dp[i+1][s'][a][b] \leftarrow dp[i][s][a][b] \\ \end{aligned}

  • slsu=11s_l s_u = 11，只能不放，故有：

dp[i+1][s′][a][b]←dp[i][s][a][b]\begin{aligned} dp[i+1][s'][a][b] \leftarrow dp[i][s][a][b] \\ \end{aligned}

最后答案为 dp[H∗W][(1<<W)−1]dp[H*W][(1<<W)-1]。

类似题目：HDU1400 Mondriaan’s Dream

Code

Tiling Dominoes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

int H, W, T;

void add(LL& a, LL b) { a = a + b; }

signed main() {
    while (cin >> H >> W) {
        if (W > H) swap(H, W);
        LL dp[2][1 << W];
        memset(dp, 0, sizeof(dp));
        dp[0][(1 << W) - 1] = 1;
        bool tag = 0;
        for (int i = 1; i <= H; i++)
            for (int j = 1; j <= W; j++) {
                tag ^= 1;
                memset(dp[tag], 0, sizeof(dp[tag]));
                for (int s = 0; s < (1 << W); s++) {
                    int nxtS = ((s << 1) & ((1 << W) - 1));
                    int sUp = (s >> (W - 1)) | (i == 1);
                    int sLeft = (s & 1) | (j == 1);
                    if (!sUp)
                        add(dp[tag][nxtS | 1], dp[tag ^ 1][s]);
                    else if (!sLeft) {
                        add(dp[tag][nxtS | 3], dp[tag ^ 1][s]);
                        add(dp[tag][nxtS], dp[tag ^ 1][s]);
                    } else
                        add(dp[tag][nxtS], dp[tag ^ 1][s]);
                }
            }
        cout << dp[tag][(1 << W) - 1] << endl;
    }
    return 0;
}

C Campus Design

Desciption

题目链接

Solution

限制了 1∗11*1 的方块的使用次数，同时有一些方格已被占用。虽然增加了一些约束，但解法和第一题基本相同，不再赘述。

Code

Campus Design
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;

const int MOD = 1E9 + 7;
int H, W, C, D;

void add(int& a, int b) { a = (a + b) % MOD; }

signed main() {
    ios::sync_with_stdio(false);
    while (cin >> H >> W >> C >> D) {
        int dp[2][1 << W][D + 1];
        char c[H + 1][W + 1];
        for (int i = 1; i <= H; i++)
            for (int j = 1; j <= W; j++) cin >> c[i][j];
        memset(dp, 0, sizeof(dp));
        dp[0][(1 << W) - 1][0] = 1;
        bool tag = 0;
        for (int i = 1; i <= H; i++)
            for (int j = 1; j <= W; j++) {
                tag ^= 1;
                memset(dp[tag], 0, sizeof(dp[tag]));
                for (int s = 0; s < (1 << W); s++)
                    for (int b = 0; b <= D; b++) {
                        int nxtS = ((s << 1) & ((1 << W) - 1));
                        int sUp = (s >> (W - 1)) | (i == 1);
                        int sLeft = (s & 1) | (j == 1);
                        if (!sUp) {
                            if (c[i][j] == '1')
                                add(dp[tag][nxtS | 1][b], dp[tag ^ 1][s][b]);
                        } else if (!sLeft) {
                            if (c[i][j] == '1') {
                                add(dp[tag][nxtS | 3][b], dp[tag ^ 1][s][b]);
                                if (b)
                                    add(dp[tag][nxtS | 1][b],
                                        dp[tag ^ 1][s][b - 1]);
                            }
                            add(dp[tag][nxtS | (c[i][j] == '0')][b],
                                dp[tag ^ 1][s][b]);
                        } else {
                            if (b && c[i][j] == '1')
                                add(dp[tag][nxtS | 1][b],
                                    dp[tag ^ 1][s][b - 1]);
                            add(dp[tag][nxtS | (c[i][j] == '0')][b],
                                dp[tag ^ 1][s][b]);
                        }
                    }
            }
        int ans = 0;
        for (int i = C; i <= D; i++) add(ans, dp[tag][(1 << W) - 1][i]);
        cout << ans << endl;
    }
    return 0;
}

D Hanjo 2

Desciption

题目链接

Solution

参考 AA 题的做法，容易想到 O(2HHW)O(2^HHW) 的 DPDP，我们只需要根据前 HH 个砖块的占用情况进行状态转移，但这样不好优化，因为有换行的情况。

如果我们每次都考虑一行的状态，设上一行状态 SS，当前行状态 TT，那么有 dp[i][T]←C(T,S)∗dp[i−1][S]dp[i][T] \leftarrow C(T,S) * dp[i-1][S]，其中 CC 是一个转移矩阵。当 T,ST,S 确定，C(T,S)C(T,S) 也就确定了，我们可以 O(4H)O(4^H) 枚举 S,TS,T 来求解 CC（为了避免重复，我们规定上一行没有被填充的部分只能用一个竖着的 2*1 的砖块填充）。求出 CC 后便可用矩阵快速幂在 O(8HlogW)O(8^HlogW) 时间内求得 dp[W]dp[W]。

Code

Hanjo 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 998244353;
int H, N;
int f[7] = {1, 1, 2, 3, 5, 8, 13};
LL W;

struct matrix {
    int r, c;
    LL m[66][66];

    matrix(int a, int b) {
        r = a, c = b;
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++) m[i][j] = 0;
    }

    LL *operator[](int i) { return m[i]; }
    friend matrix operator*(matrix &a, matrix &b) {
        matrix d(a.r, b.c);
        for (int i = 0; i < a.r; i++)
            for (int j = 0; j < b.c; j++)
                for (int k = 0; k < a.c; k++)
                    d[i][j] = (d[i][j] + a[i][k] * b[k][j] % MOD) % MOD;
        return d;
    }
};

matrix qpow(matrix A, LL b) {
    matrix ans(N, N);
    for (int i = 0; i < N; i++) ans[i][i] = 1;
    matrix base = A;
    while (b) {
        if (b & 1) ans = ans * base;
        base = base * base, b >>= 1;
    }
    return ans;
}

signed main() {
    cin >> H >> W;
    N = (1 << H);
    matrix s0(N, 1);
    s0[N - 1][0] = 1;
    matrix trans(N, N);
    for (int t = 0; t < N; t++) {      // new state
        for (int s = 0; s < N; s++) {  // old state
            int len = 0, tmp = 1;
            bool ok = 1;
            for (int i = 0, a, b; i < H; i++) {
                a = (t >> i) & 1;
                b = (s >> i) & 1;
                if (!a && !b) {
                    ok = 0;
                    break;
                } else if (a && b) {
                    len++;
                    if (i == H - 1) tmp *= f[len];
                } else {
                    tmp *= f[len];
                    len = 0;
                }
            }
            if (ok) trans[t][s] = tmp % MOD;
        }
    }
    matrix tmp = qpow(trans, W);
    matrix res = tmp * s0;
    cout << res[N - 1][0] % MOD;
    return 0;
}