地宫夺宝(三种方法)（第五届蓝桥杯省赛C++A/B/C组,第五届蓝桥杯省赛JAVAB/C组）
创始人
2024-05-04 19:53:45
0次

 PS:方法一和方法看起来复杂，但其实较容易理解，大家不要跳过哦。至于方法三的动态规划则可能有点抽象，理解起来有点难度。

目录

题目描述：

三种方法：

方法一：暴力枚举（该方法只能获得30分）

思路：

详细代码：

方法二：暴力枚举+记忆化搜索（该方法可获得满分）

思路：

详细代码：

方法三：动态规划（该方法可获得满分）

思路：

 详细代码：

题目描述：

三种方法：

对于这个题目

博主在这里介绍三种不同的方法

方法一：暴力枚举（该方法只能获得30分）

该方法是对于实在没有时间

或者想不到要怎么进行下一步而提供的

骗分的方法（有时候的几十分就一个奖项等级的差距）

思路：

如果大家实在是没有思路的话

就建议大家直接采用暴力

主要的思路就是暴力枚举

每一种从左上角到右下角的方法

然后对合法的方法相加

详细代码：

#include
using namespace std;
const int N=56;
const int Mo=1000000007;int a[N][N];int n,m,k;//h表示行，l表示列，Have表示目前有多少个宝物，MaxVal表示所持的物品中物品最大的价值为多少
int dg(int h,int l,int Have,int MaxVal){//对于合法的方案数的判断，注意不要漏掉到达出口也可以取出口的宝物的情况if(h==n&&l==m&&(Have==k||(MaxValn||l>m||Have>k) {return 0; }//不选（h,j）上的宝物的情况int NotChoose=(dg(h+1,l,Have,MaxVal)+dg(h,l+1,Have,MaxVal))%Mo;int Choose=0;//选择（h,j）上的宝物的情况if(MaxVal>n>>m>>k;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);a[i][j]++;//把所有宝贝的价格都加1，方便处理}int ans=dg(1,1,0,0)%Mo;cout<

方法二：暴力枚举+记忆化搜索（该方法可获得满分）

方法二则就是在方法一的基础上

加上了记忆化搜索

提高了算法的效率

思路：

对于在方法一中的暴力枚举

我们可以发现其实很多步骤

会进行重复计算

所以我们把方案数记录下来

可以节省很多的时间

注意这里的recorded数组记录下来的

是从recorded[h][l][Have][MaxVal]到

出口合法的方案数

详细代码：

#include
#include
#include
using namespace std;
const int N=56;
const int M=16;
const int Mo=1000000007;int a[N][N];
int recorded[N][N][M][M];int n,m,k;//h表示行，l表示列，Have表示目前有多少个宝物，MaxVal表示所持的物品中物品最大的价值为多少
int dg(int h,int l,int Have,int MaxVal){//对于合法的方案数的判断，注意不要漏掉到达出口也可以取出口的宝物的情况if(h==n&&l==m&&(Have==k||(MaxValn||l>m||Have>k) {recorded[h][l][Have][MaxVal]=0;return 0; }//如果曾经被记忆过则直接使用if(-1!=recorded[h][l][Have][MaxVal]) return recorded[h][l][Have][MaxVal];//不选（h,j）上的宝物的情况int NotChoose=(dg(h+1,l,Have,MaxVal)+dg(h,l+1,Have,MaxVal))%Mo;int Choose=0;//选择（h,j）上的宝物的情况if(MaxVal>n>>m>>k;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);a[i][j]++;}//将recorded都赋值为-1，方便后期进行判断memset(recorded,-1,sizeof(recorded));int ans=dg(1,1,0,0)%Mo;cout<

方法三：动态规划（该方法可获得满分）

思路：

方法三则是使用动态规划

进行解题

利用四维数组递推每一种合法的方法

 详细代码：

#include
using namespace std;const int N=56;
const int M=16;
const int Mo=1000000007;int f[N][N][M][M];
//f[i][j][u][v]:i和j表示位置，u表示取了u个物品，v表示取的物品中的最高价值
int a[N][N];int main(){int n,m,k;cin>>n>>m>>k;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>a[i][j];a[i][j]++;//为了方便处理边界，将每件物品的价值+1}//初始化方法数：f[1][1][1][a[1][1]]=1;//让第(1,1)位置，取该位置上的宝贝的方案数为1f[1][1][0][0]=1;//让第(1,1)位置，不取该位置上的宝贝的方案数为1for(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++){//i和j表示位置，u表示取了u个物品，v表示取的物品中的最高价值int &now=f[i][j][u][v];//别名，相当于用now代表了f[i][j][u][v]//不取a[i][j]的方案数now=(now+f[i-1][j][u][v])%Mo;//加上 从下边到达(i,j) 并不取该位置的宝贝的方案数now=(now+f[i][j-1][u][v])%Mo;//加上 从左边到达(i,j) 并不取该位置的宝贝的方案数//取a[i][j]，那么该位置的价值一定为a[i][j]，因为a[i][j]为取的物品中的最高价值if(v==a[i][j]){//这里没有判断u等于0的情况是因为u=0时v=0，不会进入判断for(int tv=0;tv

PS:比赛场上遇见题目，我们的目标并不是去找到每一个题目的最优解，而是找到对于我们来说能够快速做出题目，并能够获取高分的题目。希望大家都能获得一个满意的成绩。

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：随机数 - 时间种子的方案与实践

下一篇：数学建模学习笔记-算法（线性规划模型）-上

相关内容

热门资讯

微信安卓系统转苹果系统,轻松实... 你有没有想过，从微信安卓系统转到苹果系统，这中间的转换过程，就像是一场说走就走的旅行，充满了未知和惊...
如何刷安卓8.0系统,安卓8.... 你有没有想过，让你的安卓手机升级到最新的8.0系统，让它焕发出全新的活力呢？别急，今天我就来给你详细...
安卓系统里查看路由,安卓系统下... 你是不是也和我一样，对家里的无线网络充满了好奇？想知道安卓手机里怎么查看路由器信息？那就跟着我一起探...
手机出现安卓系统信号,手机信号... 你有没有发现，最近你的安卓手机信号好像变得特别不稳定呢？是不是觉得有时候信号满格，却还是接不到电话，...
创维安卓系统怎么安装,享受智能... 你家的创维电视是不是最近有点儿不给力，想要给它来个升级，让它焕发新生呢？那就得给它装个安卓系统啦！别...
中兴刷原生安卓系统,原生安卓系... 亲爱的读者们，你是否厌倦了那些千篇一律的安卓系统，想要给你的手机来点新鲜感？今天，就让我带你一起探索...
云系统与安卓系统软件,构建智能... 你有没有想过，你的手机里那些神奇的软件，其实都是靠云系统和安卓系统软件的默契配合才变得如此强大呢？想...
如何禁止安卓系统联网,全方位操... 你有没有想过，你的安卓手机其实是个小宇宙，里面藏着无数的秘密和信息？但是，你知道吗？有时候，这些信息...
a安卓系统不兼容,揭秘a设备的... 最近是不是发现你的安卓手机有些不对劲？比如，某个APP突然罢工了，再比如，你下载了一个新游戏，结果发...
安卓系统刷固件教程,解锁设备潜... 你有没有想过，你的安卓手机其实就像一个隐藏着无限可能的宝藏呢？没错，就是那个你每天不离手的宝贝。今天...
电脑系统安卓界面,功能与美学的... 你有没有发现，现在手机和电脑的界面越来越像了呢？没错，就是那个我们每天都要打交道的好伙伴——安卓界面...
吃鸡王座安卓系统,登顶吃鸡巅峰 你有没有想过，在手机游戏中，谁才是真正的“吃鸡王座”呢？今天，就让我带你一探究竟，看看安卓系统上的那...
安卓点名系统下载,安卓点名系统... 你有没有想过，在繁忙的学习生活中，有没有一种神奇的工具，能让你轻松管理课堂纪律，还能让点名变得如此有...
手机安装通用安卓系统,引领智能... 你有没有想过，为什么你的手机可以安装那么多好玩的应用？秘密就在于它搭载了通用安卓系统！想象一个系统就...
安卓系统仿真器,功能与操作指南 你有没有想过，在电脑上也能玩安卓游戏？没错，这就是安卓系统仿真器的神奇之处！想象你坐在电脑前，手握鼠...
安卓系统可以刷街机,畅享虚拟游... 你知道吗？现在用安卓系统刷街机，简直就像变魔术一样神奇！没错，就是那种让你仿佛穿越回童年，手握游戏杆...
安卓系统画画软件画笔,绘制无限... 你有没有发现，手机里的画画软件越来越丰富啦？尤其是安卓系统上的那些，简直让人眼花缭乱。今天，就让我带...
安卓系统垃圾和缓存,提升使用体... 手机里的安卓系统是不是越来越慢了？是不是觉得打开一个应用都要等半天？别急，今天就来跟你聊聊安卓系统里...
安卓系统图片转入苹果,轻松实现... 你是不是也有过这样的烦恼？手机里存了好多珍贵的照片，突然想换手机，却发现安卓系统的照片怎么也弄不到苹...
华为matebooke装安卓系... 你有没有想过，你的华为MateBook也能装上安卓系统呢？没错，就是那个我们平时手机上用的安卓系统！...