第五届蓝桥杯C++B组:地宫取宝

X王有一个地下宝库。是n×m个格子的矩阵。在每个格子里放一个宝藏。每件宝物都标有价格。

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

小明被带到地宫的出口,国君要求他只能向右或向上走。

当你走过一个格子时,若是阿谁格子里的宝藏的价格高于小明手里的肆意宝藏的价格,小明就能够把它捡起来(固然,他能够拿也能够不拿)。

小明走到门口的时候,若是手里的宝贝正好是K块,能够送给小明。

请帮小明做数学。在给定的情况下,他有几种差别的动作计划来得到那个k宝。

[数据形式]

输出一行3个整数,用空: n m k (1

旁边有n行数据,每行有M个整数CI(0

恳求输入一个整数,并显示刚好代表K个宝藏的动作方案数量。那个数能够很大,能够输入模1000000007的成果。

例如,输出:

2 2 2

1 2

2 1

应该输入以下挨次:

2

例如,输出:

2 3 2

1 2 3

2 1 5

应该输入以下挨次:

14

本钱协议:

峰值内存消耗

CPU消耗

请严酷根据要求输入,不存在类似“请输出...”的多余物量。

一切都放在一个同一的源文件里,调试好之后,复造并提交源代码。

留意:主函数需要去0。

留意:只利用ANSI C/ANSI C++标准,不需要调用依赖编译的十分规函数或者操做细碎。

留意:所有依赖函数必需清晰地呈现在源文件# include 中;,不克不及通过工程设置装备摆设省略常用的头文件。

提交时,留意选择所需的编译器示例。

参考代码:

//地宫寻宝(超时)#include<cstdio>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);//(坐标x, 坐标y, 最年夜值, 物品数) // max取-1,因为第一个点代价可以是0,可是可以取 printf("%lld\n", ans); return 0;}

参考代码2(dfs优化,接纳镜像递归):

#include<cstdio>#include<cstring>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]); } } //dfs(0, 0, -1, 0);//(坐标x, 坐标y, 最年夜值, 物品数) // max取-1,因为第一个点代价可以是0,可是可以取 memset(cache, -1, sizeof(cache)); printf("%lld\n", dfs2(0, 0, -1, 0)); return 0;}

您可以还会对下面的文章感兴趣:

最新评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。