1212. 地宫取宝

题目链接：

https://www.acwing.com/problem/content/description/1214/

题解：

DP问题混合怪兽

AC代码：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 55,K = 13,C = 14,MOD = 1000000007;

int f[N][N][K][C];
int w[N][N];

int main(){
    
    int n,m,k;
    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;
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(i == 1 && j == 1) continue;
            for(int u = 0;u <= k;u++){
                for(int v = 0;v <= 13;v++){
                    int & val = f[i][j][u][v];
                    val = (val + f[i-1][j][u][v]) % MOD;
                    val = (val + f[i][j-1][u][v]) % MOD;
                    if(u > 0 && v == w[i][j]){
                        for(int cc = 0;cc < w[i][j]; cc++){
                            val = (val + f[i-1][j][u-1][cc]) % MOD;
                            val = (val + f[i][j-1][u-1][cc]) % MOD;
                        }    
                    }
                }
            }
        }
    
    int res = 0;
    for(int i=0;i<=13;i++){
        res = (res + f[n][m][k][i]) % MOD;
    }
    cout << res << endl;
    return 0;
}