AcWing 1212. 地宫取宝
原题链接
中等
作者:
不知名的fE
,
2024-11-22 16:13:16
,
所有人可见
,
阅读 1
样例
import java.util.*;
public class Main {
static final int N = 55, MOD = 1000000007;
static int[][] g = new int[N][N];
static int[][][][] f = new int[N][N][15][15];
static int n, m, k;
/*
f[i][j][u][v] : 走到(i, j)位置的时候时有u件物品且最大价值的物品的价值为v的路线数量
初始化
f[1][1][1][g[1][1]] = 1;
f[1][1][0][0] = 1;//u = 0 一件物品没拿,但是由于物品的价值是从0开始的,本来应该是
f[1][1][0][-1] = 1,由于数组特性不能为负数,因此在读入数据时会有1的偏移量,使-1偏移为0
状态转移:
f[i][j][u][v] 首先分为大类选不选(i, j)的物品,
不选的话有路线:f[i - 1][j][u][v] + f[i][j - 1][u][v]种
选择的话有前提条件:u > 0(u == 0无意义) && g[i][j] == v(选择(i, j)的物品需要v与(i, j)的价值相等)
即f[i][j][u][g[i][j]](参考上升子序列问题:最后的价值一定要是g[i][j])
枚举小于v的两个方向即可
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt(); m = sc.nextInt(); k = sc.nextInt();
sc.nextLine();
for (int i = 1; i <= n; i++) g[i] = toArr(sc.nextLine().split(" "));//内部会有1的偏移量
f[1][1][1][g[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[] t = f[i][j][u];
t[v] = (t[v] + f[i - 1][j][u][v]) % MOD;
t[v] = (t[v] + f[i][j - 1][u][v]) % MOD;
if (u > 0 && g[i][j] == v)
for (int c = 0; c < v; c++) {
t[v] = (t[v] + f[i - 1][j][u - 1][c]) % MOD;
t[v] = (t[v] + f[i][j - 1][u - 1][c]) % MOD;
}
}
}
int res = 0;
//i也可以从1开始,因为价值都是大于1的只要选择了物品(k > 0)就不会出现v[0] != 0的情况
for (int i = 0; i <= 13; i++) res = (res + f[n][m][k][i]) % MOD;
System.out.println(res);
}
static int[] toArr(String[] str) {
int[] res = new int[N];
for (int i = 1; i <= m; i++) res[i] = Integer.parseInt(str[i - 1]) + 1;
return res;
}
}