---
title: "地宫取宝"
created: 2025-11-28
tags:
  - 算法
---

# 地宫取宝

## 题目 [地宫取宝](https://www.acwing.com/problem/content/1214/)

![[image-9cfb65ed.png]]

## 思路分析

![[image-6b5f92ff.png]]

## 代码实现

```cpp
#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-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/简单DP相关模型/线性dp/最长上升子序列模型练习/导弹防御系统|导弹防御系统]]