地宫取宝

题目 地宫取宝

思路分析

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=55,mod=1000000007;

int w[N][N];

int f[N][N][13][14];

int n,m,k;

int main()

{

    cin>>n>>m>>k;

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

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

            cin>>w[i][j];

            w[i][j]++;

        }

    }

    f[1][1][1][w[1][1]]=1;//左上角取的情况

    f[1][1][0][0]=1;//左上角不取的情况 原本第四维为-1 全体偏移1

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

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

            for(int u=0;u<=k;u++){

                for (int v=0;v<=13;v++){

                    //不取的两种情况 3个加起来再模会绕int一圈导致出错

                    f[i][j][u][v]=(f[i][j][u][v]+f[i-1][j][u][v])%mod;

                    f[i][j][u][v]=(f[i][j][u][v]+f[i][j-1][u][v])%mod;

                    if(u>0 && v==w[i][j]){//只有满足当前位置为最大值才可以取

                        for(int c=0;c<v;c++){//从小于它的情况转移来

                            f[i][j][u][v]=(f[i][j][u][v]+f[i-1][j][u-1][c])%mod;

                            f[i][j][u][v]=(f[i][j][u][v]+f[i][j-1][u-1][c])%mod;

                        }

                    }

                }

            }

        }

    }

    int res=0;

    for(int i=0;i<=13;i++)

        res=(res+f[n][m][k][i])%mod;

    cout<<res;

    return 0;

}

同类题型

视频讲解

⬅️ 合唱队形 🏠 00-刷题理模型 ➡️ 导弹防御系统