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

栏目: Java · 发布时间: 5年前

内容简介:X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。地宫的入口在左上角,出口在右下角。小明被带到地宫的入口,国王要求他只能向右或向下行走。

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

再例如,输入:

2 3 2

1 2 3

2 1 5

程序应该输出:

14

简单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];
    }
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

C语言从入门到精通

C语言从入门到精通

王娣//韩旭 / 清华大学 / 2010-7 / 49.80元

《C语言从入门到精通》从初学者的角度出发,以通俗易懂的语言,丰富多彩的实例,详细介绍了使用C语言进行程序开发应该掌握的各方面知识。全书共分17章,包括C语言概述,算法,数据类型,运算符与表达式,常用的数据输入、输出函数,选择结构程序设计,循环控制,数组,函数,指针,结构体和共用体,位运算,预处理,文件,存储管理,网络套接字编程和学生成绩管理系统等。所有知识都结合具体实例进行介绍,涉及的程序代码给出......一起来看看 《C语言从入门到精通》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换