企业官网建设流程全解析

地宫探宝(C++/Py/Java/Js/Go)题解

华为笔试真题 7月24号 非AI方向第三题 300分题型

题目内容

你在玩地宫探宝游戏，地宫中每块地砖上都有不同价值的财宝，每回合你有三种走法：

1. 移动到下一块地砖
2. 跳过下一块地砖，移动到第二块地砖
3. 跳过下面的第一、第二块地砖，移动到第三块地砖
   请在回合数耗尽前，携带最多的财宝逃离地宫。
   设定：
4. 逃离失数：回合数耗尽仍未到达最后一块地砖（起点在地宫之外，目的地是最后一块地砖）
5. 自动拾取落脚地砖上的财宝
6. 地砖按照直线排列

输入描述

nnn（地砖个数，取值[5,10000][5,10000][5,10000]）mmm（回合数上限，取值[2,5000]）
nnn个整数（空格分割，表示每块地砖上财宝价值，取值[0,5][0,5][0,5]）
注意：所有的输入均为整数，用空格分割，题目保证输入合法，无需校验输入

输出描述

输出：携带的财宝总价（要求找到财宝总价最大值），如无法逃离则返回−1-1−1

样例1

输入

5 3 1 2 1 1 3

输出

6

说明
第一行：有5块地砖，要求3步逃离 第二行：5个整数，分别表示地砖上的财宝价值
最优走法： 第一步：第二块地砖，拾取价值为2的财宝 第二步：第三块或第四块，拾取价值为1的财宝 第三步：第五块地砖，拾取价值为3的财宝
财宝价值共计：6

样例2

输入

10 3 0 0 3 1 2 3 0 0 0 0

输出

-1

说明
回合数是3，最大移动距离是9，无法在回合数耗尽前逃离

题解

思路

思路:动态规划

1. 移动过程中存在两个状态
   • 当前所处位置
   • 当前已用回合
2. 通过可定义状态数组dp[i][j]表示使用i回合到达j能获得的最大财宝，初始化全部设置为-INF表示不可达
3. 对第一轮进行初始化，第一次可以走1格到达0，2格到达1，3格到达2，因此设置dp[1][0]=a[0], dp[1][1] = a[1], dp[1][2] = a[2]
4. 枚举轮数为[2,m]进行状态转移，对于当前dp[i][j]j位置在上轮可达情况下，的状态转移为
   • 走一步dp[i+1][j + 1] = max(dp[i+1][j + 1], dp[i][j] + a[j+1])
   • 走一步dp[i+1][j + 2] = max(dp[i+1][j + 2], dp[i][j] + a[j+2])
   • 走一步dp[i+1][j + 3] = max(dp[i+1][j + 3], dp[i][j] + a[j+3])
5. 按照上述如果每一轮n-1位置可达，更新记录能取得的最大值。
6. 同时考虑到状态转移只发生在上一轮和当前轮，可采用滚动数组pre,cur进行空间压缩。
7. 上述代码平均时间复杂度为O(nm)

C++

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intn,m;cin>>n>>m;vector<int>value(n);for(inti=0;i<n;i++){cin>>value[i];}// 无法逃离if(m*3<n){cout<<-1;return0;}// 不可达标志constintNEG=-1e9;// pre上回合 cur当前回合 到达i能获得的最大价值vector<int>pre(n,NEG),cur(n,NEG);if(n>=1)pre[0]=value[0];if(n>=2)pre[1]=value[1];if(n>=3)pre[2]=value[2];intans=NEG;ans=max(ans,pre[n-1]);// 枚举回合, 进行状态转移for(intstep=2;step<=m;step++){fill(cur.begin(),cur.end(),NEG);// 枚举当前位置for(inti=0;i<n;i++){if(pre[i]==NEG){continue;}// 枚举当前能走到的位置for(intd=1;d<=3;d++){intnx=i+d;if(nx>=n){break;}cur[nx]=max(cur[nx],pre[i]+value[nx]);}}ans=max(ans,cur[n-1]);swap(pre,cur);}cout<<ans;return0;}

java

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();intm=sc.nextInt();int[]value=newint[n];for(inti=0;i<n;i++){value[i]=sc.nextInt();}// 无法逃离if(m*3<n){System.out.println(-1);return;}// 不可达标志finalintNEG=-1000000000;// pre：上回合；cur：当前回合，到达i能获得的最大价值int[]pre=newint[n];int[]cur=newint[n];Arrays.fill(pre,NEG);Arrays.fill(cur,NEG);if(n>=1)pre[0]=value[0];if(n>=2)pre[1]=value[1];if(n>=3)pre[2]=value[2];intans=NEG;ans=Math.max(ans,pre[n-1]);// 枚举回合，进行状态转移for(intstep=2;step<=m;step++){Arrays.fill(cur,NEG);// 枚举当前位置for(inti=0;i<n;i++){if(pre[i]==NEG){continue;}// 枚举当前能走到的位置for(intd=1;d<=3;d++){intnx=i+d;if(nx>=n){break;}cur[nx]=Math.max(cur[nx],pre[i]+value[nx]);}}ans=Math.max(ans,cur[n-1]);int[]temp=pre;pre=cur;cur=temp;}System.out.println(ans);}}

python

n,m=map(int,input().split())value=list(map(int,input().split()))# 无法逃离ifm*3<n:print(-1)exit()# 不可达标志NEG=-10**9# pre上回合 cur当前回合 到达i能获得的最大价值pre=[NEG]*n cur=[NEG]*nifn>=1:pre[0]=value[0]ifn>=2:pre[1]=value[1]ifn>=3:pre[2]=value[2]ans=NEG ans=max(ans,pre[n-1])# 枚举回合，进行状态转移forstepinrange(2,m+1):cur=[NEG]*n# 枚举当前位置foriinrange(n):ifpre[i]==NEG:continue# 枚举当前能走到的位置fordinrange(1,4):nx=i+difnx>=n:breakcur[nx]=max(cur[nx],pre[i]+value[nx])ans=max(ans,cur[n-1])pre,cur=cur,preprint(ans)

javascript

constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});constinput=[];rl.on("line",(line)=>{input.push(line);});rl.on("close",()=>{const[n,m]=input[0].split(" ").map(Number);constvalue=input[1].split(" ").map(Number);// 无法逃离if(m*3<n){console.log(-1);return;}// 不可达标志constNEG=-1000000000;// pre上回合 cur当前回合 到达i能获得的最大价值letpre=newArray(n).fill(NEG);letcur=newArray(n).fill(NEG);if(n>=1)pre[0]=value[0];if(n>=2)pre[1]=value[1];if(n>=3)pre[2]=value[2];letans=NEG;ans=Math.max(ans,pre[n-1]);// 枚举回合，进行状态转移for(letstep=2;step<=m;step++){cur.fill(NEG);// 枚举当前位置for(leti=0;i<n;i++){if(pre[i]===NEG){continue;}// 枚举当前能走到的位置for(letd=1;d<=3;d++){constnx=i+d;if(nx>=n){break;}cur[nx]=Math.max(cur[nx],pre[i]+value[nx]);}}ans=Math.max(ans,cur[n-1]);lettemp=pre;pre=cur;cur=temp;}console.log(ans);});

Go

packagemainimport("bufio""fmt""os")funcmax(a,bint)int{ifa>b{returna}returnb}funcmain(){in:=bufio.NewReader(os.Stdin)varn,mintfmt.Fscan(in,&n,&m)value:=make([]int,n)fori:=0;i<n;i++{fmt.Fscan(in,&value[i])}// 无法逃离ifm*3<n{fmt.Println(-1)return}// 不可达标志constNEG=-1000000000// pre上回合 cur当前回合 到达i能获得的最大价值pre:=make([]int,n)cur:=make([]int,n)fori:=0;i<n;i++{pre[i]=NEG cur[i]=NEG}ifn>=1{pre[0]=value[0]}ifn>=2{pre[1]=value[1]}ifn>=3{pre[2]=value[2]}ans:=NEG ans=max(ans,pre[n-1])// 枚举回合，进行状态转移forstep:=2;step<=m;step++{fori:=0;i<n;i++{cur[i]=NEG}// 枚举当前位置fori:=0;i<n;i++{ifpre[i]==NEG{continue}// 枚举当前能走到的位置ford:=1;d<=3;d++{nx:=i+difnx>=n{break}cur[nx]=max(cur[nx],pre[i]+value[nx])}}ans=max(ans,cur[n-1])pre,cur=cur,pre}fmt.Println(ans)}