# 蓝桥杯 2014届真题 地宫取宝 动态规划解法

2021-03-02 21:48:11

# 蓝桥杯 2014届真题 地宫取宝 动态规划解法

X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。

1.首先定义 dp 数组

dp[i][j][k][c]: 表示从 $$(1, 1)$$走到 $$(i,j)$$时，手里有 $$k$$ 件宝贝，且宝贝价值的最大值为 $$c$$ 时的行动方案数。

2.找到状态转移方程

// 拿走宝贝
for (int c = 0; c < cur; c++) {
dp[i][j][k][cur] += dp[i - 1][j][k - 1][c] + dp[i][j - 1][k - 1][c];
}


// 不拿走宝贝
for (int c = 0; c <= 12; c++) {
dp[i][j][k][c] += dp[i - 1][j][k][c] + dp[i][j - 1][k][c];
}


3.base case

$$(i,j)$$ 处宝贝的价值 $$a[i][j]$$ 为当 k = 1时，$$dp[i][j][1][a[i][j]]$$ 表示只选择当前宝贝，可知方案数即为从 $$(1, 1)$$走到 $$(i,j)$$ 的方案数。

// base case
dp[1][1][1][a[1][1]] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j][1][a[i][j]] += dp[i-1][j][1][a[i-1][j]] + dp[i][j-1][1][a[i][j-1]];
}
}


import java.util.Scanner;

public class Main {
static int MAXN = 50, MAXM = 50;
static int MAXK = 12, MAXC = 12;
static long[][][][] dp = new long[MAXN + 1][MAXM + 1][MAXK + 1][MAXC + 1];
static int[][] a = new int[MAXN + 1][MAXM + 1];
static int n, m, k, ans = 0, mod = 1000000007;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
k = sc.nextInt();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] = sc.nextInt();

// base case
dp[1][1][1][a[1][1]] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (!(i == 1 && j == 1)) {
dp[i][j][1][a[i][j]] += dp[i-1][j][1][a[i-1][j]] + dp[i][j-1][1][a[i][j-1]];
dp[i][j][1][a[i][j]] %= mod;
}

for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int l = 1; l <= k; l++) {
int cur = a[i][j];
// 拿走宝贝
for (int c = 0; c < cur; c++) {
dp[i][j][l][cur] += dp[i-1][j][l-1][c] + dp[i][j-1][l-1][c];
dp[i][j][l][cur] %= mod;
}
// 不拿走宝贝
for (int c = 0; c <= MAXC; c++) {
dp[i][j][l][c] += dp[i-1][j][l][c] + dp[i][j-1][l][c];
dp[i][j][l][c] %= mod;
}
}

for (int c = 0; c <= MAXC; c++) {
ans += dp[n][m][k][c];
ans %= mod;
}

System.out.println(ans);
}
}


https://www.cnblogs.com/Code-CHAN/p/14471491.html