//卡壳点：m写成了n，这也是高频卡壳错误，需要优先检查
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int mod = 1000000007;int n,m,k; int f[55][55][15][15]; int w[55][55]; 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][0][0] = 1; f[1][1][1][w[1][1]] = 1; for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){//卡壳点：m写成了n这也是高频卡壳错误 if(i == 1 && j == 1)continue; for(int a = 0;a <= k;a++){ for(int b = 0;b <= 13;b++){ int &val = f[i][j][a][b] ; val = (val + f[i][j-1][a][b]) % mod; val = (val + f[i-1][j][a][b]) % mod; if(a > 0 && b < w[i][j]){ int &vall = f[i][j][a][w[i][j]]; vall = (vall + f[i][j-1][a-1][b]) % mod; vall = (vall + f[i-1][j][a-1][b]) % mod; } } } } } int res = 0; for (int i = 0; i <= 13; i ++ ) res = (res + f[n][m][k][i]) % mod; cout << res << endl; }
思路
// // 数据范围
// 1≤n,m≤50
// ,
// 1≤k≤12
// ,
// 0≤Ci≤12
// // 范围小，不用在意
// // 他有多少种不同的行动方案能获得这 k
// // 件宝贝。
// // 切入点 求满足条件的方案数量 dp，枚举，dfs
// dp
// 状态表示 集合 坐标，最大价值，数量 ，四维数组表示f[i][j][k][w] 走到i，j时k件物品，最大价值为w的方案数
// 需要用0作第四维下标来表示还没有选，因此w读入时要++
// 属性 数量
// 状态计算 集合划分 最后一个不一样的点 f[i][j][k][w];
// 拿I,J f[i-1][j][k-1][0~w[i][j]-1];
// f[i][j-1][k-1][0~w[i][j]-1];
// 不拿i，j f[i-1][j][k][0~13];
// f[i][j-1][k][0~13];
// 所有方案相加得f[i][j]，两两相加之后取模
// // 输出f[i][j][k][0~13]
// 边界初始化f[1][1][0][0] = 1;
// f[1][1][1][w[1][1]] = 1;
