蓝桥杯 历届试题 地宫取宝

 历届试题 地宫取宝   时间限制：1.0s   内存限制：256.0MB      问题描述 　　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

思路：将初始化的价值都增加1，因为迷宫中宝物的价值可能为0，要用long来存储数据，不然中间会造成溢出

AC代码：

import java.util.Scanner; public class Main { static long[][][][] visit = new long[60][60][15][15]; static int[][] map = new int[60][60]; static int[][] dir = {{0,1},{1,0}}; static int n,m,k; public static void main(String[] args) { Scanner in = new Scanner(System.in); //每一维度记录一个值，坐标x和y，携带的数量以及携带的最重的重量 n = in.nextInt(); m = in.nextInt(); k = in.nextInt(); for (int i=0; i<60; i++) { for (int j=0; j<60; j++) { for (int k=0; k<15; k++) { for (int l=0; l<15; l++) { visit[i][j][k][l] = -1; } } } } //因为宝物的价值有可能为0，不好控制，所以将初值都加1 for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { map[i][j] = in.nextInt() + 1; } } long sum = dfs(0,0,0,0); System.out.println(sum); } private static long dfs(int x, int y, int f, int l) { if (visit[x][y][f][l] != -1) return visit[x][y][f][l]; if (x == n-1 && y == m-1) { //这条路径可行，返回1 if (f == k) { return visit[x][y][f][l] = 1; } else if (f == k-1 && map[x][y] > l) { return visit[x][y][f][l] = 1; } else { return visit[x][y][f][l] = 0; } } long sum = 0; for (int i=0; i<2; i++) { int newx = x + dir[i][0]; int newy = y + dir[i][1]; if (newx >= n || newy >= m) continue; if (map[x][y] > l && f + 1 <= k) { sum += dfs(newx,newy,f+1,map[x][y]) % 1000000007; } sum += dfs(newx,newy,f,l) % 1000000007; } return visit[x][y][f][l] = sum % 1000000007; } }

思路：参考的大神的代码，加了一点注释，地址：http://blog.csdn.net/rodestillfaraway/article/details/50529814

AC代码：

#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <map> #include <cstring> #include <climits> #include <cmath> #include <cctype> typedef long long ll; using namespace std; const int mod = 1000000007; int dp[55][55][15][15];//前2个是坐标，第三个是目前取到的件数，第四个是目前的最大值 int map1[55][55]; int main() { int n,m,k; while(scanf("%d%d%d",&n,&m,&k) != EOF) { int max = 0; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { scanf("%d",&map1[i][j]); map1[i][j]++;//在这加1，是因为物品的价值有可能为0，所有物品价值数加1，不影响最后的结果 if(map1[i][j] > max) { max = map1[i][j]; } } } memset(dp,0,sizeof(dp)); dp[1][1][0][0] = 1; dp[1][1][1][map1[1][1]] = 1; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { //在这一个点不取,.总件数为0 dp[i][j][0][0] += dp[i-1][j][0][0] + dp[i][j-1][0][0];//注意是加等 dp[i][j][0][0] %= mod; for(int p=1; p<=k; p++) { //在这一点不取，总件数为p for(int val = 0; val <= max; val++) { dp[i][j][p][val] += dp[i-1][j][p][val]; dp[i][j][p][val] %= mod; dp[i][j][p][val] += dp[i][j-1][p][val]; dp[i][j][p][val] %= mod; } //到目前为止，只取1件，且目前的这一点取 if(p == 1) { dp[i][j][1][map1[i][j]] += dp[i-1][j][0][0]; dp[i][j][1][map1[i][j]] %= mod; dp[i][j][1][map1[i][j]] += dp[i][j-1][0][0]; dp[i][j][1][map1[i][j]] %= mod; } //到目前为止，只取p件，且目前的这一点取 else { for(int val = 0; val < map1[i][j]; val++) { dp[i][j][p][map1[i][j]] += dp[i-1][j][p-1][val]; dp[i][j][p][map1[i][j]] %= mod; dp[i][j][p][map1[i][j]] += dp[i][j-1][p-1][val]; dp[i][j][p][map1[i][j]] %= mod; } } } } } int sum = 0; for(int i=0; i<=max; i++) { sum += dp[n][m][k][i]; sum %= mod; } printf("%d\n",sum); } return 0; }