# 地宫取宝 X 国王有一个地宫宝库,是 n×m 个格子的矩阵,每个格子放一件宝贝,每个宝贝贴着价值标签。 地宫的入口在左上角,出口在右下角。 小明被带到地宫的入口,国王要求他只能向右或向下行走。 走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。 当小明走到出口时,如果他手中的宝贝恰好是 k 件,则这些宝贝就可以送给小明。 请你帮小明算一算,在给定的局面下,他有多少种不同的行动方案能获得这 k 件宝贝。 **输入格式** 第一行 3 个整数,n,m,k,含义见题目描述。 接下来 n 行,每行有 m 个整数 Ci 用来描述宝库矩阵每个格子的宝贝价值。 **输出格式** 输出一个整数,表示正好取 k 个宝贝的行动方案数。 该数字可能很大,输出它对 1000000007 取模的结果。 **数据范围** ``` 1≤n,m≤50, 1≤k≤12, 0≤Ci≤12 ``` **输入样例1:** ``` 2 2 2 1 2 2 1 ``` **输出样例1:** ``` 2 ``` **输入样例2:** ``` 2 3 2 1 2 3 2 1 5 ``` **输出样例2:** ``` 14 ``` 以下选项错误的是? ## aop ### before ```cpp #include using namespace std; ``` ### after ```cpp ``` ## 答案 ```cpp const int N = 55, M = 15, mod = 1e9 + 7; int w[N][N]; int memo[N][N][M][M]; int n, m, K, ans; int dfs(int i, int j, int k, int c) { if (memo[i][j][k][c] != -1) return memo[i][j][k][c]; if (i == n && j == m) { if (k == K || (k == K - 1 && w[i][j] > c)) return 1; else return 0; } int sum = 0; if (i + 1 <= n) { if (w[i][j] > c) sum = (sum + dfs(i + 1, j, k + 1, w[i][j])) % mod; sum = (sum + dfs(i + 1, j, k, c)) % mod; } if (j + 1 <= m) { if (w[i][j] > c) sum = (sum + dfs(i, j + 1, k + 1, w[i][j])) % mod; sum = (sum + dfs(i, j, k, c)) % mod; } return memo[i][j][k][c] = sum % mod; } int main() { scanf("%d %d %d", &n, &m, &K); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &w[i][j]); w[i][j]++; } } memset(memo, -1, sizeof(memo)); dfs(1, 1, 0, 0); printf("%d\n", memo[1][1][0][0]); return 0; } ``` ## 选项 ### A ```cpp int n, m, k; int data[55][55]; typedef long long LL; LL ans; LL mod = 1000000007; LL cache[55][55][15][15]; LL dfs2(int x, int y, int max, int count) { if (cache[x][y][max + 1][count] != -1) { return cache[x][y][max + 1][count]; } LL ans = 0; if (x == n || y == m || count > k) { return 0; } int cur = data[x][y]; if (x == n - 1 && y == m - 1) { if (count == k || (count == k - 1 && cur > max)) { ans++; if (ans > mod) { ans %= mod; } } return ans; } if (cur > max) { ans += dfs2(x, y + 1, cur, count + 1); ans += dfs2(x + 1, y, cur, count + 1); } ans += dfs2(x, y + 1, max, count); ans += dfs2(x + 1, y, max, count); cache[x][y][max + 1][count] = ans % mod; return ans % mod; } void dfs(int x, int y, int max, int count) { if (x == n || y == m || count > k) { return; } int cur = data[x][y]; if (x == n - 1 && y == m - 1) { if (count == k || (count == k - 1 && cur > max)) { ans++; if (ans > mod) { ans %= mod; } } } if (cur > max) { dfs(x, y + 1, cur, count + 1); dfs(x + 1, y, cur, count + 1); } dfs(x, y + 1, max, count); dfs(x + 1, y, max, count); } int main() { scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { scanf("%d", &data[i][j]); } } memset(cache, -1, sizeof(cache)); printf("%lld\n", dfs2(0, 0, -1, 0)); return 0; } ``` ### B ```cpp int n, m, k; int data[55][55]; long long ans; long long mod = 1000000007; void dfs(int x, int y, int max, int count) { if (x == n || y == m) { return; } int cur = data[x][y]; if (x == n - 1 && y == m - 1) { if (count == k || (count == k - 1 && cur > max)) { ans++; if (ans > mod) { ans %= mod; } } } if (cur > max) { dfs(x, y + 1, cur, count + 1); dfs(x + 1, y, cur, count + 1); } dfs(x, y + 1, max, count); dfs(x + 1, y, max, count); } int main() { scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { scanf("%d", &data[i][j]); } } dfs(0, 0, -1, 0); printf("%lld\n", ans); return 0; } ``` ### C ```cpp const int N = 55; const int MOD = 1e9 + 7; int dp[N][N][13][14]; int g[N][N]; int n, m, k; int main() { cin >> n >> m >> k; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> g[i][j]; g[i][j]++; } } dp[1][1][1][g[1][1]] = 1; dp[1][1][0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { for (int u = 0; u <= k; u++) { for (int v = 0; v <= 13; v++) { dp[i][j][u][v] = (dp[i][j][u][v] + dp[i - 1][j][u][v]) % MOD; dp[i][j][u][v] = (dp[i][j][u][v] + dp[i][j - 1][u][v]) % MOD; if (u > 0 && v == g[i][j]) { for (int c = 0; c < v; c++) { dp[i][j][u][v] = (dp[i][j][u][v] + dp[i - 1][j][u - 1][c]) % MOD; dp[i][j][u][v] = (dp[i][j][u][v] + dp[i][j - 1][u - 1][c]) % MOD; } } } } } } int res = 0; for (int i = 0; i <= 13; i++) res = (res + dp[n][m][k][i]) % MOD; cout << res << endl; return 0; } ```