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

zhlzt · 2023-04-25 06:36:06 · 题解

题目

有一个 n\times m 的图纸，从下往上搭积木。
每块积木必须紧挨着放置在某一块积木的正上方，最底层除外。
同一层中的积木必须连续摆放，标有 X 的位置不能放置积木。
求出放置积木的方案数，对 (10^9+7) 取模。

二维前缀和+区间 DP 做法

设 dp_{i,l,r} 表示从上往下数的第 i 层在区间 [l,r] 内放置积木且以这一层为搭的积木的顶端的方案数，只要满足区间 [l,r] 内没有 X ，就不难得出以下状态转移方程（代码中要用二维前缀和优化）：

dp_{i,l,r}=\sum_{j=1}^{l}\sum_{k=r}^{m}dp_{i+1,j,k}

设答案为 ans。先枚举搭的积木的顶端是哪一层，再枚举这一层在哪个区间内放置积木，对 dp 数组进行求和，加上一个积木都不摆放的方案数 1，得出：

ans=1+\sum_{i=1}^{n}\sum_{l=1}^{m}\sum_{r=l}^{m}dp_{i,l,r}

初始化就是给从上往下数的第 n 层即最底层所有内部没有 X 的区间 [l,r] 对应的 dp_{n,l,r} 赋初始值 1。

代码时间复杂度为 O(nm^2)，不会时间超限。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int num[110][110];char s[110];
long long dp[110][110][110],sum[110][110];
int main(){
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=m;j++)
            num[i][j]=num[i][j-1]+(s[j]=='X');//用前缀和来记录区间内是否有 X
    }
    long long ans=1;//一个积木都不摆放的方案数
    for(int l=1;l<=m;l++)
        for(int r=l;r<=m;r++){
            dp[n][l][r]=(num[n][r]-num[n][l-1]==0);
            ans=(ans+dp[n][l][r])%mod;//注意初始值也要加到 ans 上
        }
    for(int i=n-1;i>=1;i--){
        for(int l=1;l<=m;l++)
            for(int r=1;r<=m;r++)
                sum[l][r]=(dp[i+1][l][r]+sum[l][r-1]+sum[l-1][r]-sum[l-1][r-1])%mod;//用前缀和预处理来优化时间复杂度
        for(int l=1;l<=m;l++)
            for(int r=l;r<=m;r++) if(num[i][r]-num[i][l-1]==0){
                dp[i][l][r]=(sum[l][m]-sum[0][m]-sum[l][r-1]+sum[0][r-1])%mod;
                ans=(ans+dp[i][l][r])%mod;
            }
    }
    printf("%lld",(ans+mod)%mod);//由于上面加加减减又要取余，可能出现负数，所以是 (ans+mod)%mod 而不是 ans
    return 0;
}