转载

第五届蓝桥杯Java B——地宫取宝

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

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。

【数据格式】

输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12)

接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值

要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。

例如，输入：

2 2 2

1 2

2 1

程序应该输出：

再例如，输入：

2 3 2

1 2 3

2 1 5

程序应该输出：

简单DP一下就行了

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
    static int n, m, k;
    static int[][] map;
    static long[][][][] res;
    static int[][] dr = { { 1, 0 }, { 0, 1 } };
    static int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        n = cin.nextInt();
        m = cin.nextInt();
        k = cin.nextInt();
        map = new int[n][m];
        res = new long[51][51][13][14];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                map[i][j] = cin.nextInt();

        System.out.println(dfs(0, 0, 0, -1));
    }

    private static long dfs(int x, int y, int idx, int max) {
        if (res[x][y][idx][max + 1] != 0)
            return res[x][y][idx][max + 1];
        if (idx > k)
            return 0;
        long ans = 0;
        int cur = map[x][y];
        if (x == n - 1 && y == m - 1) {
            if (idx == k || (idx == k - 1 && cur > max))
                return ans = (++ans) % MOD;
        } else {
            for (int i = 0; i < 2; i++) {
                int nx = x + dr[i][0];
                int ny = y + dr[i][1];
                if (nx < n && ny < m) {
                    if (cur > max)
                        ans += dfs(nx, ny, idx + 1, cur);
                    ans += dfs(nx, ny, idx, max);
                }
            }
        }
        res[x][y][idx][max + 1] = ans % MOD;
        return res[x][y][idx][max + 1];
    }
}

原文 https://www.wmathor.com/index.php/archives/1242/

正文到此结束