蓝桥杯2018年第九届真题-搭积木(区间dp)

解题思路:
构建数组dp[i][j][k]代表第i层，积木从i到k时可能的情况种类。转移方程为dp[i][j][k]=∑dp[i-1][x][y](x<=j且y>=k),如果依照此方式转移，复杂度为O(n^5),如果我们依照前缀和的思路，即sum[i][j][k],代表第i层，积木从j开始，结尾大于等于k的所有情况和，计算此前缀和的转移方程为sum[i][j][k]=sum[i][j][k+1]+dp[i][j][k],依照这个改进，dp[i][j][k]=∑dp[i-1][x][k] (x<=j)，复杂度变为O(n^4)。
注意事项:
因为可能积木在未搭建到顶层停止和一个都不放的情况，故把dp的所有数字加起来，另外还要注意不可能的情况，即有X的位置,还要注意取模。
参考代码:

#include<bits/stdc++.h>
using namespace std;
#define maxx 110
int n,m;
string s;
int dp[maxx][maxx][maxx];
int all[maxx][maxx]; //不允许为1
int sum[maxx][maxx][maxx];
int main()
{
  cin>>n>>m;
  for(int i=n;i>=1;--i)
  {
    cin>>s;
    for(int j=1;j<=m;++j)
    if(s[j-1]=='X') all[i][j]=1;
  }

  for(int j=1;j<=m;++j)
   for(int k=j;k<=m;++k)
    {if(all[1][k]==1) break;
    for(int w=1;w<=j;++w)
    dp[1][j][k]=1;
    }

  for(int j=1;j<=m;++j)
   for(int k=m;k>=j;--k)
   sum[1][j][k]=(sum[1][j][k+1]+dp[1][j][k])%mod;

 for(int i=2;i<=n;++i)
 {
  for(int j=1;j<=m;++j)
   for(int k=j;k<=m;++k)
    {if(all[i][k]==1) break;
    for(int w=1;w<=j;++w)
    dp[i][j][k]=(dp[i][j][k]+sum[i-1][w][k])%mod;
    }
  for(int j=1;j<=m;++j)
   for(int k=m;k>=j;--k)
   sum[i][j][k]=(sum[i][j][k+1]+dp[i][j][k])%mod;

 }
 for(int i=1;i<=n;++i)
  for(int j=1;j<=m;++j)
  for(int k=j;k<=m;++k)
   ans=(ans+dp[i][j][k])%mod;
   cout<<(ans+1)%mod;
}