地宫探宝(C/Py/Java/Js/Go)题解华为笔试真题 7月24号 非AI方向第三题 300分题型题目内容你在玩地宫探宝游戏地宫中每块地砖上都有不同价值的财宝每回合你有三种走法移动到下一块地砖跳过下一块地砖移动到第二块地砖跳过下面的第一、第二块地砖移动到第三块地砖请在回合数耗尽前携带最多的财宝逃离地宫。设定逃离失数回合数耗尽仍未到达最后一块地砖起点在地宫之外目的地是最后一块地砖自动拾取落脚地砖上的财宝地砖按照直线排列输入描述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无法在回合数耗尽前逃离题解思路思路:动态规划移动过程中存在两个状态当前所处位置当前已用回合通过可定义状态数组dp[i][j]表示使用i回合到达j能获得的最大财宝初始化全部设置为-INF表示不可达对第一轮进行初始化第一次可以走1格到达02格到达13格到达2因此设置dp[1][0]a[0], dp[1][1] a[1], dp[1][2] a[2]枚举轮数为[2,m]进行状态转移对于当前dp[i][j]j位置在上轮可达情况下的状态转移为走一步dp[i1][j 1] max(dp[i1][j 1], dp[i][j] a[j1])走一步dp[i1][j 2] max(dp[i1][j 2], dp[i][j] a[j2])走一步dp[i1][j 3] max(dp[i1][j 3], dp[i][j] a[j3])按照上述如果每一轮n-1位置可达更新记录能取得的最大值。同时考虑到状态转移只发生在上一轮和当前轮可采用滚动数组pre,cur进行空间压缩。上述代码平均时间复杂度为O(nm)C#includebits/stdc.husingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intn,m;cinnm;vectorintvalue(n);for(inti0;in;i){cinvalue[i];}// 无法逃离if(m*3n){cout-1;return0;}// 不可达标志constintNEG-1e9;// pre上回合 cur当前回合 到达i能获得的最大价值vectorintpre(n,NEG),cur(n,NEG);if(n1)pre[0]value[0];if(n2)pre[1]value[1];if(n3)pre[2]value[2];intansNEG;ansmax(ans,pre[n-1]);// 枚举回合, 进行状态转移for(intstep2;stepm;step){fill(cur.begin(),cur.end(),NEG);// 枚举当前位置for(inti0;in;i){if(pre[i]NEG){continue;}// 枚举当前能走到的位置for(intd1;d3;d){intnxid;if(nxn){break;}cur[nx]max(cur[nx],pre[i]value[nx]);}}ansmax(ans,cur[n-1]);swap(pre,cur);}coutans;return0;}javaimportjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnsc.nextInt();intmsc.nextInt();int[]valuenewint[n];for(inti0;in;i){value[i]sc.nextInt();}// 无法逃离if(m*3n){System.out.println(-1);return;}// 不可达标志finalintNEG-1000000000;// pre上回合cur当前回合到达i能获得的最大价值int[]prenewint[n];int[]curnewint[n];Arrays.fill(pre,NEG);Arrays.fill(cur,NEG);if(n1)pre[0]value[0];if(n2)pre[1]value[1];if(n3)pre[2]value[2];intansNEG;ansMath.max(ans,pre[n-1]);// 枚举回合进行状态转移for(intstep2;stepm;step){Arrays.fill(cur,NEG);// 枚举当前位置for(inti0;in;i){if(pre[i]NEG){continue;}// 枚举当前能走到的位置for(intd1;d3;d){intnxid;if(nxn){break;}cur[nx]Math.max(cur[nx],pre[i]value[nx]);}}ansMath.max(ans,cur[n-1]);int[]temppre;precur;curtemp;}System.out.println(ans);}}pythonn,mmap(int,input().split())valuelist(map(int,input().split()))# 无法逃离ifm*3n:print(-1)exit()# 不可达标志NEG-10**9# pre上回合 cur当前回合 到达i能获得的最大价值pre[NEG]*n cur[NEG]*nifn1:pre[0]value[0]ifn2:pre[1]value[1]ifn3:pre[2]value[2]ansNEG ansmax(ans,pre[n-1])# 枚举回合进行状态转移forstepinrange(2,m1):cur[NEG]*n# 枚举当前位置foriinrange(n):ifpre[i]NEG:continue# 枚举当前能走到的位置fordinrange(1,4):nxidifnxn:breakcur[nx]max(cur[nx],pre[i]value[nx])ansmax(ans,cur[n-1])pre,curcur,preprint(ans)javascriptconstreadlinerequire(readline);constrlreadline.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);constvalueinput[1].split( ).map(Number);// 无法逃离if(m*3n){console.log(-1);return;}// 不可达标志constNEG-1000000000;// pre上回合 cur当前回合 到达i能获得的最大价值letprenewArray(n).fill(NEG);letcurnewArray(n).fill(NEG);if(n1)pre[0]value[0];if(n2)pre[1]value[1];if(n3)pre[2]value[2];letansNEG;ansMath.max(ans,pre[n-1]);// 枚举回合进行状态转移for(letstep2;stepm;step){cur.fill(NEG);// 枚举当前位置for(leti0;in;i){if(pre[i]NEG){continue;}// 枚举当前能走到的位置for(letd1;d3;d){constnxid;if(nxn){break;}cur[nx]Math.max(cur[nx],pre[i]value[nx]);}}ansMath.max(ans,cur[n-1]);lettemppre;precur;curtemp;}console.log(ans);});Gopackagemainimport(bufiofmtos)funcmax(a,bint)int{ifab{returna}returnb}funcmain(){in:bufio.NewReader(os.Stdin)varn,mintfmt.Fscan(in,n,m)value:make([]int,n)fori:0;in;i{fmt.Fscan(in,value[i])}// 无法逃离ifm*3n{fmt.Println(-1)return}// 不可达标志constNEG-1000000000// pre上回合 cur当前回合 到达i能获得的最大价值pre:make([]int,n)cur:make([]int,n)fori:0;in;i{pre[i]NEG cur[i]NEG}ifn1{pre[0]value[0]}ifn2{pre[1]value[1]}ifn3{pre[2]value[2]}ans:NEG ansmax(ans,pre[n-1])// 枚举回合进行状态转移forstep:2;stepm;step{fori:0;in;i{cur[i]NEG}// 枚举当前位置fori:0;in;i{ifpre[i]NEG{continue}// 枚举当前能走到的位置ford:1;d3;d{nx:idifnxn{break}cur[nx]max(cur[nx],pre[i]value[nx])}}ansmax(ans,cur[n-1])pre,curcur,pre}fmt.Println(ans)}
