2018年第九届蓝桥杯国赛-E. 搭积木

题面

原题链接

【问题描述】

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

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

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

• 规则1：每块积木必须紧挨着放置在某一块积木的正上方，与其下一层的积木对齐；
• 规则2：同一层中的积木必须连续摆放，中间不能留有空隙；
• 规则3：小明不喜欢的位置不能放置积木。

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

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

由于这个答案可能很大，你只需要回答这个答案对1000000007(十亿零七)取模后的结果。

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

【输入格式】

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

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

【输出格式】

输出一个整数，表示答案对1000000007取模后的结果。

【样例输入1】

2 3
..X
.X.

【样例输出1】

4

【样例说明1】

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

..X
.X.

..X
OX.

O.X
OX.

..X
.XO

【样例输入2】

3 3
..X
.X.
...

【样例输出2】

16

【数据规模约定】

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

对于40%的数据，$n<=10,m\le30$；

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

思路

动态规划

记 $f[i][j][k]$ 表示 第 i 行，从第 j 列开始摆放到第 k 列的方案数量，$sx[i][j]$ 表示第 i 行的前 j 列有多少个 ’ X’，则其状态转移方程如下：

$f[i][j][k] = \begin{cases} 0, & sx[i][k] - sx[i][j - 1] \ne 0 \\ \sum_{1 \le p\le i,j\le q \le m} f[i][p][q], & sx[i][k] - sx[i][j - 1] = 0 \end{cases}$

最终答案即为遍历 $f[i][j][k]$ 的和。

但是若直接使用上面的状态转移方程，复杂度为 $O(n\times m^4)$，需要优化，我们用 $s[i][j]$ 来表示 包含区间 $[1, i] \times [1, j]$ 的面积区域（二维前缀和），可以将代码的时间复杂度优化到 $O(n\times m^2)$。

代码

#include<iostream>
#include<cstdio>

using namespace std;
typedef long long LL;
const int N = 105, MOD = 1e9 + 7;
int m, n;
char g[N];
LL f[N][N][N];    //f[i][j][k]表示 第 i 行，从第 j 列开始摆放到第 k 列的方案数量
LL s[N][N];
int sx[N][N];

int main() {
    scanf("%d%d", &m, &n);
    for (int i = m; i; i--) {
        scanf("%s", g + 1);
        for (int j = 1; j <= n; j++) {
            sx[i][j] = sx[i][j - 1] + (g[j] == 'X' ? 1 : 0);
        }
    }

    //初始化第 0 层的方案数目
    LL res = 1;
    f[0][1][n] = 1;
    for (int i = 1; i <= m; i++) {
        for (int l = 1; l <= n; l++) {
            for (int r = 1; r <= n; r++) {
                s[l][r] = (s[l - 1][r] + s[l][r - 1] - s[l - 1][r - 1] + f[i - 1][l][r]) % MOD;
            }
        }

        for (int j = 1; j <= n; j++) {
            for (int k = j; k <= n; k++) {
                if (sx[i][k] - sx[i][j - 1] == 0) {
                    f[i][j][k] = (s[j][n] - s[j][k - 1] - s[0][n] + s[0][k - 1]) % MOD;
                    res = (res + f[i][j][k]) % MOD;
                }
            }
        }
    }
    cout << (res + MOD) % MOD << endl;

    return 0;
}