自动搬运

查看原文

来自洛谷，原作者为

	zhlzt Light in the eyes.

搬运于2025-08-24 22:41:21，当前版本为作者最后更新于2023-04-25 06:36:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目

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

二维前缀和+区间 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;
}