题解不多说了大家写的都很好
我注意的几个点
1. 首先是价值偏移量,题目中给出的0 - 12 很坑坑在初始化上了
2. 如果没有偏移量那么我们会发现初始状态的选和不选都是一个状态方程式
3. 第二点 u也就是这题目中的 已经得到宝物的数目 在去判断要不要拿的时候一定要u > 0 是因为它一定是从u - 1的状态中转移过来的为什么不能是从0呢? 因为如果是0 那么u - 1 是一个负数不可能的
4. 最后就是最长上升子序列问题啦,它必然是需要k个物品的价值大于前面物品的价值才可以拿下
#include <iostream>
#include <cstring>
using namespace std;
const int N = 55, M = 15, MOD = 1e9 + 7;
int f[N][N][M][M];
int w[N][N];
int n, m, k;
int res;
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;
}
}
}
}
for(int i = 0;i <= 13;i ++) res = (res + f[n][m][k][i]) % MOD;
cout << res << endl;
return 0;
}