题目描述



题目分析

使用动态规划,设 $dp[l][r]$ 为当前层积木/区间/包含 [l, r] 的方案数,注意是包含,则状态转移方程为
$dp[l][r]+=dp[l-1][r]+dp[l][r+1]-dp[l-1][r+1]$
因为 $dp[l-1][r]+dp[l][r+1]$ 中包括 $dp[l-1][r+1]+dp[l][r]$,所以要减去 $dp[l-1,r+1]$,
那么对于第 h 层如果区间 [l, r] 可以放置积木,ans 就加上第 h-1 层的 $dp[l][r]$,
[l, r] 中是否有 ‘X’ 使用前缀和的思想保存在 check 数组中。

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
#include<iostream>
#include<cstdio>
using namespace std;
const int N=101,MOD=1000000007;

int check[N][N]; //判断是否存在'X'
long long dp[N][N]; //当前层积木区间包含[l,r]的方案数,注意是包含

int main()
{
int n,m;
cin>>n>>m;
char str[N];
for(int i=n;i>0;i--) {
scanf("%s",str+1);
for(int j=1;j<=m;j++) {
check[i][j]=check[i][j-1];
if(str[j]=='X') {
check[i][j]++;
}
}
}
long long ans=1; //什么都不放也是一种方案
for(int l=1;l<=m;l++) { //初始化第1层
for(int r=m;r>=l;r--) {
if(check[1][r]-check[1][l-1]==0) { //不存在'X'
ans++;
dp[l][r]=1+dp[l-1][r]+dp[l][r+1]-dp[l-1][r+1];
}
}
}
for(int i=2;i<=n;i++) {
for(int l=1;l<=m;l++) {
for(int r=m;r>=l;r--) {
if(check[i][r]-check[i][l-1]==0) {
ans=(ans+dp[l][r])%MOD;
dp[l][r]=(dp[l][r]+dp[l-1][r]+dp[l][r+1]-dp[l-1][r+1])%MOD;
}
else {
dp[l][r]=0;
}
}
}
}
cout<<ans<<endl;

return 0;
}