地宫夺宝(三种方法)（第五届蓝桥杯省赛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”。

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

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

相关内容

热门资讯

安卓系统自带的网页,功能与特色... 你有没有发现，每次打开安卓手机，那熟悉的系统界面里总有一个默默无闻的小家伙——安卓系统自带的网页浏览...
美咖云系统安卓版,开启智能生活... 你有没有发现，最近手机上多了一个叫“美咖云系统安卓版”的小家伙？它就像一个魔法师，轻轻一点，就能让你...
安卓系统推荐最好的手机,盘点性... 你有没有想过，拥有一部性能卓越的手机，就像是拥有了移动的宝藏库？在这个信息爆炸的时代，一部好手机不仅...
安卓11系统能精简吗,释放潜能 你有没有发现，随着手机越来越智能，系统也越来越庞大？安卓11系统，这个最新的操作系统，是不是也让你觉...
安卓自动重启系统软件,揭秘原因... 手机突然自动重启，是不是感觉整个人都不好了？别急，今天就来和你聊聊这个让人头疼的安卓自动重启系统软件...
苹果手机x刷安卓系统,探索安卓... 你有没有想过，你的苹果手机X竟然也能刷上安卓系统？是的，你没听错，就是那个一直以来都和我们苹果手机X...
安卓系统智商低吗,智商低下的真... 你有没有想过，为什么安卓系统的智商总被调侃得好像有点低呢？是不是觉得它总是慢吞吞的，有时候还犯点小错...
安卓系统手机联系人,揭秘你的社... 你有没有发现，手机里的联系人列表就像是一个小小的社交圈呢？里面藏着我们的亲朋好友、工作伙伴，甚至还有...
安卓系统免费铃声下载,打造个性... 手机里那首老掉牙的铃声是不是让你觉得有点out了呢？别急，今天就来给你支个招，让你轻松给安卓手机换上...
安卓系统用哪个桌面好,打造个性... 你有没有发现，手机桌面可是我们每天都要面对的“脸面”呢？换一个好看的桌面，心情都能跟着好起来。那么，...
虚拟大师是安卓10系统,功能与... 你知道吗？最近在手机圈里，有个新玩意儿引起了不小的轰动，那就是虚拟大师！而且，更让人惊喜的是，这个虚...
安卓系统与苹果优缺点,系统优缺... 说到手机操作系统，安卓和苹果绝对是两大巨头，它们各有各的特色，就像两道不同的美味佳肴，让人难以抉择。...
安卓win双系统主板,融合与创... 你有没有想过，一台电脑如果既能流畅运行安卓系统，又能轻松驾驭Windows系统，那该有多爽啊？没错，...
安卓系统可精简软件,轻松提升手... 你有没有发现，手机里的安卓系统越来越庞大，软件也越装越多，有时候感觉手机就像个“大肚子”，不仅运行速...
安卓系统基于linux的代码,... 你有没有想过，那个陪伴你每天刷抖音、玩游戏、办公的安卓系统，其实背后有着一套复杂的基于Linux的代...
苹果和安卓的拍照系统,谁更胜一... 你有没有发现，现在手机拍照已经成为我们生活中不可或缺的一部分呢？无论是记录生活的点滴，还是捕捉美丽的...
苹果和安卓系统不同吗,系统差异... 你有没有想过，为什么你的手机里装的是苹果的iOS系统，而朋友的手机却是安卓系统呢？这两种系统，看似都...
安卓系统有多少级,揭秘其多级架... 你有没有想过，那个陪伴我们日常生活的安卓系统，它其实有着丰富的层级结构呢？没错，就是那个让我们的手机...
华为鸿蒙系统与安卓的,技术融合... 你知道吗？最近科技圈可是炸开了锅，华为鸿蒙系统与安卓的较量成为了大家热议的话题。这不，今天我就来给你...
什么安卓手机是苹果系统,搭载苹... 你有没有想过，为什么有些人宁愿花大价钱买苹果手机，而有些人却对安卓手机情有独钟呢？其实，这个问题背后...