[蓝桥杯 2018 国 B] 搭积木

GitHub 跳转原题关系图返回列表

把每一层看成连续区间，设 dp[l][r] 表示上一层支撑区间为 [l,r] 的方案数，再用区间包含和转到下一层。

OJ: luogu

题目 ID: P8675

难度:普及+/提高

标签:动态规划计数dp区间dp

日期: 2026-06-19 19:05

题意

第 0 层地基固定是一整段长度为 m 的积木。

之后每一层如果要放积木，必须放成一个连续区间，并且这一整段都要落在下一层支撑区间的正上方；同时，这一层对应位置不能有 X。

问一共有多少种搭法。空方案也算一种。

思路

最直接的思路是递归：当前上一层支撑区间是 [L, R]，下一层就枚举所有合法子区间 [l, r]，或者直接停止。

先看一个可以直接验证想法的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

static int n, m;
static vector<string> grid;

bool ok(int row, int l, int r) {
    for (int i = l; i <= r; ++i) {
        if (grid[row][i] == 'X') {
            return false;
        }
    }
    return true;
}

int dfs(int row, int l, int r) {
    if (row > n) {
        return 1;
    }

    long long ways = 1; // 从这一层开始不再继续放。

    for (int nl = l; nl <= r; ++nl) {
        for (int nr = nl; nr <= r; ++nr) {
            if (!ok(row, nl, nr)) {
                continue;
            }
            ways += dfs(row + 1, nl, nr);
        }
    }

    return ways % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    grid.assign(n + 1, string(m + 1, '.'));
    vector<string> rows(n + 1);
    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        rows[i] = s;
    }
    for (int i = 1; i <= n; ++i) {
        string s = rows[n - i + 1];
        for (int j = 1; j <= m; ++j) {
            grid[i][j] = s[j - 1];
        }
    }

    cout << dfs(1, 1, m) % MOD << '\n';
    return 0;
}

brute.cpp 会直接枚举“下一层放哪一段”，适合小数据对拍，但正式数据下会反复搜索大量相同状态。

关键观察是：每一层的状态只和“上一层是哪一段连续区间”有关。因此设 dp[l][r] 表示上一层支撑区间恰好是 [l, r] 的方案数。

如果本层想放区间 [nl, nr]，它能接收的方案数就是所有包含它的上一层区间方案数之和。也就是说，我们需要快速求：

所有满足 L <= nl 且 R >= nr 的 dp[L][R] 之和

这张表说明几个典型状态的含义：

状态	表示什么
`dp[1][m]`	地基整段作为上一层支撑区间
`dp[2][4]`	上一层恰好搭成了区间 `[2,4]` 的方案数
`next_dp[2][4]`	当前层区间 `[2,4]` 的方案数

读这张表时，关键是理解 dp[l][r] 表示“上一层支撑是什么”，而不是“当前层已经结束”。正因为层与层之间只有“区间包含”关系，所以可以用一个二维包含和把所有父区间的方案数一次性加起来。

实现时，先由上一层 dp 构造 cover_sum[l][r]，表示所有能覆盖 [l, r] 的上一层方案数之和；再判断这一层 [l, r] 是否全是 .，如果合法，就令 next_dp[l][r] = cover_sum[l][r]。所有 next_dp 都可以加入答案，因为在这一层停止同样是合法方案。

DP 公式

设 $dp_{l,r}$ 表示上一层支撑区间恰好是 $[l,r]$ 的方案数。当前层想放区间 $[nl,nr]$ 时，需要统计所有能覆盖它的上一层区间：

next_{nl,nr}=\sum_{L\leqslant nl,\ R\geqslant nr} dp_{L,R}

代码用二维包含和快速得到这个求和。每一层所有合法的 $next_{l,r}$ 都可以加入答案：

ans\leftarrow ans+\sum_{l\leqslant r} next_{l,r}

公式解释：下一层区间必须被上一层区间覆盖。next_{l,r} 因此等于所有父区间方案数之和，二维包含和只是把这个求和加速；每个合法当前区间都可以作为最终停止层。

代码

cpp

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
78
79#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

static long long dp[105][105];
static long long next_dp[105][105];
static long long cover_sum[105][105];
static int bad_prefix[105][105];
static char grid[105][105];

bool ok(int row, int l, int r) {
    return bad_prefix[row][r] - bad_prefix[row][l - 1] == 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<string> rows(n + 1);
    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        rows[i] = s;
    }
    for (int i = 1; i <= n; ++i) {
        string s = rows[n - i + 1];
        for (int j = 1; j <= m; ++j) {
            grid[i][j] = s[j - 1];
            bad_prefix[i][j] = bad_prefix[i][j - 1] + (grid[i][j] == 'X');
        }
    }

    // 第 0 层地基固定是整段 [1, m]。
    dp[1][m] = 1;
    long long ans = 1; // 什么都不放也算一种。

    for (int row = 1; row <= n; ++row) {
        for (int l = 1; l <= m; ++l) {
            for (int r = m; r >= 1; --r) {
                long long val = dp[l][r];
                if (l > 1) {
                    val = (val + cover_sum[l - 1][r]) % MOD;
                }
                if (r < m) {
                    val = (val + cover_sum[l][r + 1]) % MOD;
                }
                if (l > 1 && r < m) {
                    val = (val - cover_sum[l - 1][r + 1] + MOD) % MOD;
                }
                cover_sum[l][r] = val;
            }
        }

        for (int l = 1; l <= m; ++l) {
            for (int r = l; r <= m; ++r) {
                if (!ok(row, l, r)) {
                    next_dp[l][r] = 0;
                    continue;
                }
                next_dp[l][r] = cover_sum[l][r];
                ans = (ans + next_dp[l][r]) % MOD;
            }
        }

        for (int l = 1; l <= m; ++l) {
            for (int r = 1; r <= m; ++r) {
                dp[l][r] = next_dp[l][r];
                next_dp[l][r] = 0;
                cover_sum[l][r] = 0;
            }
        }
    }

    cout << ans % MOD << '\n';
    return 0;
}

复杂度

每一层处理 $O(m^2)$ 个区间，构造包含和和转移都在 $O(m^2)$ 内完成，所以总时间复杂度是 $O(n * m^2)$ ，空间复杂度是 $O(m^2)$ 。

总结

这题的关键是把每一层抽象成一个连续区间。抽象之后，层与层之间只剩下“子区间被父区间包含”的关系，计数 DP 就很自然了。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P8675 [蓝桥杯 2018 国 B] 搭积木

题目描述

小明对搭积木非常感兴趣。他的积木都是同样大小的正立方体。

在搭积木时，小明选取 $m$ 块积木作为地基，将他们在桌子上一字排开，中间不留空隙，并称其为第 $0$ 层。

随后，小明可以在上面摆放第 $1$ 层，第 $2$ 层，……，最多摆放至第 $n$ 层。摆放积木必须遵循三条规则：

规则 $1$ ：每块积木必须紧挨着放置在某一块积木的正上方，与其下一层的积木对齐；

规则 $2$ ：同一层中的积木必须连续摆放，中间不能留有空隙；

规则 $3$ ：小明不喜欢的位置不能放置积木。

其中，小明不喜欢的位置都被标在了图纸上。图纸共有 $n$ 行，从下至上的每一行分别对应积木的第 $1$ 层至第 $n$ 层。每一行都有 $m$ 个字符，字符可能是 . 或 X，其中 X 表示这个位置是小明不喜欢的。

现在，小明想要知道，共有多少种放置积木的方案。他找到了参加蓝桥杯的你来帮他计算这个答案。

由于这个答案可能很大，你只需要回答这个答案对 $1000000007(10^9+7)$ 取模后的结果。

注意：地基上什么都不放，也算作是方案之一种。

输入格式

输入数据的第一行有两个正整数 $n$ 和 $m$ ，表示图纸的大小。

随后 $n$ 行，每行有 $m$ 个字符，用来描述图纸。每个字符只可能是 . 或 X。

输出格式

输出一个整数，表示答案对 $10^9+7$ 取模后的结果。

输入输出样例 #1

输入 #1

text

1
2
32 3
..X
.X.

输出 #1

text

说明/提示

【样例解释】

成功的摆放有（其中O表示放置积木）：

text

1
2
3 1       2       3       4
..X     ..X     O.X     ..X
.X.     OX.     OX.     .XO

【数据约定】

对于 $10\%$ 的数据， $n=1$ ， $m \le 30$ ；

对于 $40\%$ 的数据， $n \le 10$ ， $m \le 30$ ；

对于 $100\%$ 的数据， $n \le 100$ ， $m \le 100$ 。

时限 1 秒, 256M。蓝桥杯 2018 年第九届国赛

[蓝桥杯 2018 国 B] 搭积木

目录

题意

思路

DP 公式

代码

复杂度

总结

一图流解析