蓝桥杯地宫取宝记忆深度搜索+两种dp解法

曾经终败给现在 2023-07-13 15:27 17阅读 0赞

## 蓝桥杯 地宫取宝 记忆深度搜索+两种dp解法 ##

资源限制  
时间限制：1.0s 内存限制：256.0MB  
问题描述  
　　X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。  
输入格式  
　　输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12)

接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值  
输出格式  
　　要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。  
　　  
样例输入  
2 2 2  
1 2  
2 1  
样例输出  
2  
样例输入  
2 3 2  
1 2 3  
2 1 5  
样例输出  
14

看到这个题目就想到dp,但是写了一下转移方程发现写不出，看了题解用了记忆化搜索，原理就是记忆已经计算过的dfs，也是很常用的一种方法。一开始觉得深搜有点难写，看规模还拿不了太多分，所以就没往深搜想，后来听说暴力深搜也能拿60分。

### 1. 记忆化搜索 ###

#include<bits/stdc++.h>
    using namespace std;
    #define LL long long
    #define MOD 1000000007
    int n,m,k;
    int mm[55][55];
    LL cache[55][55][15][15];
    
    LL sum=0;
    LL dfs(int x,int y,int maxs,int cnt){
        //点到终点的方案数
        if(cache[x][y][maxs][cnt]!=-1)
            return cache[x][y][maxs][cnt];
    
        if(x==n||y==m||cnt>k)
            return cache[x][y][maxs][cnt]=0;
        LL s=0;
    
        if(x==n-1&&y==m-1)
            if(cnt==k||(cnt==k-1&&mm[x][y]>maxs))
                return cache[x][y][maxs][cnt]=1;
    
    
        if(mm[x][y]>maxs){
        
            s+=dfs(x+1,y,mm[x][y],cnt+1);
            s%=MOD;
            s+=dfs(x,y+1,mm[x][y],cnt+1);
            s%=MOD;
        }
        s+=dfs(x+1,y,maxs,cnt);
        s%=MOD;
        s+=dfs(x,y+1,maxs,cnt);
        s%=MOD;
        return cache[x][y][maxs][cnt]=s;
    }
    
    int main(){
        
        cin>>n>>m>>k;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++){
        
                cin>>mm[i][j];
                mm[i][j]++;
             }
        memset(cache,-1,sizeof (cache));
    
        printf("%lld\n",dfs(0,0,0,0));
    
    
    }

此处有个小变化，将输入数据整体+1,使其范围变为从1开始，这样可以定义无拿取的点的最大价值为0.

### 2.dp(略走弯路) ###

写完了记忆化搜索，感觉dp还是可以，于是又想了想。  
写出dp公式

对于一个已知的点dp\[i\]\[j\]\[k\]\[l\]要转移只有两个方向，每个方向只有两种可能，拿或者不拿。

此时我们认为不取的状态数为0，也就是k==0时，dp恒为0 注意此处，我在此处走了弯路。如果那么思考问题将会复杂很多。

那么dp\[i\]\[j\]\[1\]\[m\[i\]\[j\]\]的初值需要我们赋值，观察到对于每一条终点为i,j的路径，都对应着一种方案，该种方案k=1,l=m\[i\]\[j\]即为取该点本身。也就是初值应当赋值为终点为i，j的路径数量。问题转化为求终点为i，j的路径数量，考虑需要横向操作j-1次，纵向操作i-1次，求组合。也就是

( n + m − 2 ) ! ( n − 1 ) ! ( m − 1 ) ! = C ( m + n − 2 , n − 1 ) = C ( m + n − 2 , m − 1 ) \\frac\{(n+m-2)!\}\{(n-1)!(m-1)!\}=C(m+n-2,n-1)=C(m+n-2,m-1) (n−1)!(m−1)!(n\+m−2)!=C(m\+n−2,n−1)=C(m\+n−2,m−1)

问题变为组合数取余，m,n数量不大，使用杨辉三角的公式就可以求解  
 C ( n , m ) = C ( n − 1 , m ) + C ( n − 1 , m − 1 ) C(n,m)=C(n-1,m)+C(n-1,m-1) C(n,m)=C(n−1,m)\+C(n−1,m−1)  
赋初值后，再进行以下dp

如果不取，则能更新以下状态  
 d p \[ i + 1 \] \[ j \] \[ k \] \[ l \] + = d p \[ i \] \[ j \] \[ k \] \[ l \] dp\[i+1\]\[j\]\[k\]\[l\]+=dp\[i\]\[j\]\[k\]\[l\] dp\[i\+1\]\[j\]\[k\]\[l\]\+=dp\[i\]\[j\]\[k\]\[l\]  
 d p \[ i \] \[ j + 1 \] \[ k \] \[ l \] + = d p \[ i \] \[ j \] \[ k \] \[ l \] dp\[i\]\[j+1\]\[k\]\[l\]+=dp\[i\]\[j\]\[k\]\[l\] dp\[i\]\[j\+1\]\[k\]\[l\]\+=dp\[i\]\[j\]\[k\]\[l\]

如果取，还要更新以下状态  
 d p \[ i + 1 \] \[ j \] \[ k \] \[ m m \[ i + 1 \] \[ j \] \] + = d p \[ i \] \[ j \] \[ k − 1 \] \[ l \] ; dp\[i+1\]\[j\]\[k\]\[mm\[i+1\]\[j\]\]+=dp\[i\]\[j\]\[k-1\]\[l\]; dp\[i\+1\]\[j\]\[k\]\[mm\[i\+1\]\[j\]\]\+=dp\[i\]\[j\]\[k−1\]\[l\];  
 d p \[ i \] \[ j + 1 \] \[ k \] \[ m m \[ i \] \[ j + 1 \] \] + = d p \[ i \] \[ j \] \[ k − 1 \] \[ l \] ; dp\[i\]\[j+1\]\[k\]\[mm\[i\]\[j+1\]\]+=dp\[i\]\[j\]\[k-1\]\[l\]; dp\[i\]\[j\+1\]\[k\]\[mm\[i\]\[j\+1\]\]\+=dp\[i\]\[j\]\[k−1\]\[l\];

#include<bits/stdc++.h>
    using namespace std;
    #define LL long long
    #define MOD 1000000007
    int n,m,kk;
    int mm[55][55];
    LL dp[55][55][15][15];//i,j 处 取k个 最大值l
    LL C[105][105];
    
    void init(){
        
        C[0][0]=1;
        for(int i=1;i<=100;i++){
        
            C[i][0]=C[i][i]=1;
            for(int j=1;j<=i/2+1;j++)
                C[i][j]=C[i][i-j]=(C[i-1][j-1]+C[i-1][j])%MOD;
    
        }
    }
    int main(){
        
        init();
        cin>>n>>m>>kk;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
        
                cin>>mm[i][j];
                mm[i][j]++;
                dp[i][j][1][mm[i][j]]=C[i+j-2][i-1];
               
             }
    
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                for(int k=1;k<=12;k++)
                    for(int l=0;l<=13;l++){
        
                        dp[i+1][j][k][l]+=dp[i][j][k][l];dp[i+1][j][k][l]%=MOD;
                        dp[i][j+1][k][l]+=dp[i][j][k][l];dp[i][j+1][k][l]%=MOD;
                        if(mm[i+1][j]>l)
                            dp[i+1][j][k][mm[i+1][j]]+=dp[i][j][k-1][l];dp[i+1][j][k][mm[i+1][j]]%=MOD;
                        if(mm[i][j+1]>l)
                            dp[i][j+1][k][mm[i][j+1]]+=dp[i][j][k-1][l];dp[i][j+1][k][mm[i][j+1]]%=MOD;
                    }
            
            LL ans=0;
            for(int i=0;i<=13;i++)
                ans+=dp[n][m][kk][i],ans%=MOD;
        printf("%lld\n",ans);
    
    
    }

### 3.dp(正解 我猜的 ) ###

方程和上面无差，主要在取个数为0的时候，考虑这种情况不是0，也就是说认为一个都不取也是一种方案

为什么要那么考虑？上面做法k从1开始考虑，似乎没有问题，但是对于k=1时的初始值运用了组合数进行运算，组合数还略显麻烦。不如考虑将动态规划延伸到k=0进行统一。

现在难以解决的是k=1的情况，k=1的情况是从哪来的呢，一种思路就是上面组合数求，另一种，认为k=1的情况是根据转移方程来的，也就是k=1来自上一个位置的k=0的方案数，那k=0的方案数又是怎么来的，k=0相当于，上两个位置k=0之后，这一次也没有拿的情况，也就是将上两个位置上的k=0的方案数相加，其实际意义就和组合数意义一样，啥也不选，值为起点到该点的路径数量。

由此避开了复杂的组合数运算，此题中组合数运算还不算麻烦，只是普通杨辉三角，数量大了就要用卢卡斯定理，但是不管怎么说，各种意义上都是下面的方法来的优秀。

通过对几行代码的修改，就可以完全避免篇幅巨大的组合数取模运算。

#include<bits/stdc++.h>
    using namespace std;
    #define LL long long
    #define MOD 1000000007
    int n,m,kk;
    int mm[55][55];
    LL dp[55][55][15][15];//i,j 处 取k个 最大值l的方案数
    
    int main(){
        
        cin>>n>>m>>kk;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
        
                cin>>mm[i][j];
                mm[i][j]++;
             }
    
    
        dp[1][1][0][0]=dp[1][1][1][mm[1][1]]=1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                for(int k=0;k<=12;k++)
                    for(int l=0;l<=13;l++){
        
                        dp[i+1][j][k][l]+=dp[i][j][k][l];dp[i+1][j][k][l]%=MOD;
                        dp[i][j+1][k][l]+=dp[i][j][k][l];dp[i][j+1][k][l]%=MOD;
                        if(mm[i+1][j]>l)
                            dp[i+1][j][k][mm[i+1][j]]+=dp[i][j][k-1][l];dp[i+1][j][k][mm[i+1][j]]%=MOD;
                        if(mm[i][j+1]>l)
                            dp[i][j+1][k][mm[i][j+1]]+=dp[i][j][k-1][l];dp[i][j+1][k][mm[i][j+1]]%=MOD;
                    }
    
            LL ans=0;
            for(int i=0;i<=13;i++)
                ans+=dp[n][m][kk][i],ans%=MOD;
        printf("%lld\n",ans);
    
    
    }

当然，可能dp还能优化，因为看到了求和 和 状态大部分只使用一次，但是因为到了四维，我已经想象不出来了。。。但是总有大佬能超越维度。。。。暂且先这样吧