地宫秘宝
作者:
恒_41
,
2024-04-08 19:42:20
,
所有人可见
,
阅读 2
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 55;
const int M = 15;
const int MOD = 1e9 + 7;
int a[N][N];
int f[N][N][M][M];
int main() {
int n, m,c;
cin >> n >> m >> c;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
a[i][j]++;//使每个物品的价值都加一,空出价值为0的物品表示没选物品
}
f[1][1][1][a[1][1]] = 1;
f[1][1][0][0] = 1;//初始化起点选和不选两种
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int cnt = 0; cnt <= c; cnt++) {
for (int k = 0; k < M; k++) {//枚举每行,每列,走到该点是手上有几件物品,最后一件物品的价值
f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i - 1][j][cnt][k]) % MOD;
//对于每个物品,都有取或不取两种选择,而不取是肯定可以的,要取的话,要满足背包能放下这个条件
f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i][j - 1][cnt][k]) % MOD;
//这里先处理肯定存在的两种情况,直接加入f
if (a[i][j] == k && cnt > 0){//cnt-1下标必须>=0所以要求第二个条件——cnt>0
//再处理两种不一定存在的情况——取a[i][j],必须满足取完后最后一个物品的价值必须要为k,因为在k的循环内部,对于每一个k,已经确定
//在满足if要求的条件下,选取价值为k的物品,枚举选取这个物品前最后一个物品的价值(0-k-1)
for (int s = 0; s < k; s++) {//把从上/左来的且选a[i][j]的情况进一步划分,在上一个状态,手上的物品价值为0-k-1的所有可能
f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i-1][j][cnt-1][s]) % MOD;
f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i][j-1][cnt-1][s]) % MOD;
}
}
}
}
}
}
int res = 0;
for (int i = 1; i < M; i++) {
res = (res+f[n][m][c][i])%MOD;
}
cout << res << endl;
}