蓝桥杯2018年第九届真题-搭积木-题解（C++代码）

解题思路:

首先根据题目中的规则一，可以推出在搭积木是底层就决定上层的宽度。那我们可以把解决问题的出发点定义在最下层。先把最下层的字符根据X划分成多个连续.的区间，然后讨论每个区间满足其他规则的数目，然后运算（这里还不能确定相加）。

对于每个确定宽度区间，我们可以从一遍进行搜索，当然也不是盲目搜索。如果使用单纯的搜索的话，其中会存在大量重复搜索的数据，这些重复的数据会大大提高搜索的时间，于是我们采用记忆化搜索，就是将已经搜索过的位置进行数据保存保存在一个二维数组中（dp[b][c]在二维数组中，b代表第几列，c代表第几层）

对于在搜索的方向，我是从右到左。当搜索到（b,c)的时候，当前列的高度就确定了，那么改变摆放积木的方法的数量只与右边相邻的一列有关，dp[b][c]+=dp[b][h[b]](h数组保存某一列可到达最高的高度。)

规则二：同一层积木必须连续摆放，这就是表明在一段区间内的积木摆放情况不会存在每列最高的积木先下降后上升。对于这个的规则，我们还要加一个判断。判断的方法不知一种，我的方法是在刚才的dp数组的基础上在加一维，变成三维数组。dp[a][b][c]b，c表示含义不变。a有两个值，一个是0代表前面已经出现下降不能再有上升，另一个是1代表前面没出现下降。

在进行搜索过程中就需要判断a是否为0。如果是0：dp[a][b][c]+=dp[a][b+1][c],如果是1：dp[a][b][c]+=dp[a][b+1][c]

规则二还有一部分就是中间不能有空隙，说明两个独立的区间不能同时摆放，也就是不同区间的计算结果进行相加。

规则三就是说明每一列的最高点。一位在“X”的上面的.是不能摆放积木的（如果摆放就违反规则一）。

注意事项:
对于规则二判断下降的方法，可以使用一个标记数字。当题目给出的n,m太大时，我的方法可能会内存超限。
参考代码:

#include"iostream"

#include"cstdio"

#include"string.h"

#define mod 1000000007

using namespace std;

int n,m,r,h[1000],num=0;

int dp[3][100][100];

char s[1000][1000];

void col_height(){

    for(int i=1;i<=m;i++){

        int hi=0;

        for(int j=n;j>=1;j--){

            if(s[j][i]=='X')

                break;

            hi++;

        }

        h[i]=hi;

    }

    return ;

}

int dfs(int sta,int pos,int last){

    if(pos>r){

        return 1;

    }

    if(dp[sta][pos][last]!=-1)

        return dp[sta][pos][last];

    int sum=0;

    for(int i=1;i<=h[pos];i++){

        if(i>last){

            if(sta==1)

                sum=(sum+dfs(1,pos+1,i))%mod;

        }else if(i==last){

            sum=(sum+dfs(sta,pos+1,i))%mod; 

        }else

            sum=(sum+dfs(0,pos+1,i))%mod; 

     }

    return dp[sta][pos][last]=sum;

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++){

        for(int j=1;j<=m;j++){

            cin>>s[i][j];

        }

    }

    col_height();

    int i=1;

    while(i<=m){

        if(s[n][i]=='X'){

            i++;continue;

        }

        int j=i;

        while(j<=m&&s[n][j]=='.'){

            j++;continue;

        }

        j--;

        for(r=j;r>=i;r--){

            memset(dp,-1,sizeof(dp));

            for(int l=r;l>=i;l--){

                num=(num+dfs(1,l,1))%mod;

            }

        }

        i=j+1;

    }

    cout<<(num+1)%mod<<endl;

    return 0;

}