题意：

• 先导条件：给定一个数$n\times m$地图，每个格子都放有不同价值的物品，从左上角出发到右下角，每一步往右或者往下走一步，面对每一个物品，可以拿走，也可以不拿，而且只有当前格子的物品大于所有已拿的物品价值，才能够拿这个物品
• 问题：问到达终点时，恰好拿够$k$个物品的方案数

解题思路：

• 这道题可以用四维DP解决, 我们用集合的思想考虑DP
• 第一个要想清楚的就是，要取得当前格子的物品，这个物品必须比当前所拥有的物品都大，所以有一个性质：后面拿的物品比前面的物品大
• 然后画出以下的分析图：

• 难点在于状态计算部分，联想到01背包问题，对于每个物品，都有取或不取两种选择，而不取是肯定可以的，要取的话，要满足背包能放下这个条件
• 这里也一样，对于每个物品，都可以不选，也就是直接从上一步转移状态过来，但是如果要取得$(i,j)$位置的物品，就必须满足当前的$k$和$a[i][j]$相等，因为上面分析过了，如果现在取了$a[i][j]$，那么它肯定是现在所有物品最大的，这和我们一开始四维数组的定义是对应的
• 在具体的状态转移中，如果不选，就直接从上一步完完整整地把状态$cnt$和$k$转移过来；如果选，那上一步就应该选了$cnt-1$个物品，而且上一步身上所有物品最大值只能是$1\dots k-1$，把这些状态的方案数累加，就可以成为选择当前物品的条件

注意事项：

• 因为这道题的所有物品价值范围是$0\dots 12$，可以把他们全部都递增，范围就变成了$1\dots 13$，因为我们记录的是方案数，只关心各个物品之间的大小关系，具体数值不影响答案，但是这样的做法可以把$0$作为一个特殊边界来处理
• 整个过程不理解的话，可以用纸笔模拟一下，看看每个状态的数值应该是多少

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

using namespace std;

const int N = 55, mod = 1000000007;

int n, m, k;
int w[N][N];
int f[N][N][13][14];

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;

    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 c = 0; c < v; c ++ )
                        {
                            val = (val + f[i - 1][j][u - 1][c]) % mod;
                            val = (val + 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 << endl;

    return 0;
}