C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 55;
const int mod = 1e9 + 7;
int dp[N][N];
int p[N][N];
int f[N][N][15][15];

int main() {
    int n, m, k, i, j, t, w1;
    cin >> n >> m >> k;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            cin >> p[i][j];
            p[i][j]++;//关键点：因为存在价值为0的物品，如果不+1会出现这种情况：无法判断第四维=0时是没有选物品还是此时价值最大值为0。此时我们选择将所有物品价值+1，因为判断是否选取一个物品只要判断价值的相对大小。
        }
    }
    f[1][1][0][0] = 1;//没选第一个
    f[1][1][1][p[1][1]] = 1;//选择第一个
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            for (t = 0; t <= k; t++) {
                for (w1 = 0; w1 <= 13; w1++) {
                    if (j > 1) {
                        if (p[i][j] > w1) f[i][j][t][p[i][j]] = (f[i][j][t][p[i][j]]+f[i][j - 1][t - 1][w1])%mod;//选(i,j)的物品
                        f[i][j][t][w1] = (f[i][j][t][w1]+ f[i][j - 1][t][w1])%mod;//不选
                    }
                    if (i > 1) {
                        if (p[i][j] > w1) f[i][j][t][p[i][j]] = (f[i][j][t][p[i][j]]+ f[i - 1][j][t - 1][w1])%mod;//选
                        f[i][j][t][w1] = (f[i][j][t][w1]+f[i-1][j][t][w1])%mod;//不选
                    }
                }
            }
        }
    }
    int ans = 0;
    for (i = 1; i <= 13; i++) ans = (ans+f[n][m][k][i])%mod;
    cout << ans;
    return 0;
}