最新华为上机考试
真题目录：点击查看目录
华为OD面试真题精选：点击立即查看
华为OD机考双机位C卷 - 分披萨
题目描述
"吃货"和"馋嘴"两人到披萨店点了一份铁盘（圆形）披萨，并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。但是粗心的服务员将披萨切成了每块大小都完全不同奇数块，且肉眼能分辨出大小。
由于两人都想吃到最多的披萨，他们商量了一个他们认为公平的分法：从"吃货"开始，轮流取披萨。除了第一块披萨可以任意选取外，其他都必须从缺口开始选。
他俩选披萨的思路不同。"馋嘴"每次都会选最大块的披萨，而且"吃货"知道"馋嘴"的想法。
已知披萨小块的数量以及每块的大小，求"吃货"能分得的最大的披萨大小的总和。
输入描述
第 1 行为一个正整数奇数 N，表示披萨小块数量。
- 3 ≤ N < 500
接下来的第 2 行到第 N + 1 行（共 N 行），每行为一个正整数，表示第 i 块披萨的大小
- 1 ≤ i ≤ N
披萨小块从某一块开始，按照一个方向次序顺序编号为 1 ~ N
- 每块披萨的大小范围为 [1, 2147483647]
输出描述
"吃货"能分得到的最大的披萨大小的总和。
用例
输入
5821057输出
19说明：
此例子中，有 5 块披萨。每块大小依次为 8、2、10、5、7。
按照如下顺序拿披萨，可以使"吃货"拿到最多披萨：
“吃货” 拿大小为 10 的披萨
“馋嘴” 拿大小为 5 的披萨
“吃货” 拿大小为 7 的披萨
“馋嘴” 拿大小为 8 的披萨
“吃货” 拿大小为 2 的披萨
至此，披萨瓜分完毕，"吃货"拿到的披萨总大小为 10 + 7 + 2 = 19
可能存在多种拿法，以上只是其中一种。
解题思路
给定一个环形排列的披萨数组，每块披萨有一个美味值，需要计算出从任意位置开始，能够获得的最大美味值总和。
环形处理：由于披萨是环形排列的，所以在选择披萨时需要考虑边界情况，即当选择了最左边或最右边的披萨后，如何循环到另一端。
动态规划：使用一个二维数组
dp作为记忆化存储，其中dp[L][R]表示从左边界L到右边界R能够获得的最大美味值。如果dp[L][R]已经被计算过，则直接返回该值。递归计算：定义一个递归函数来计算
dp[L][R]。如果a[L]（左边界的披萨美味值）大于a[R]（右边界的披萨美味值），则选择L并将L向右移动一位；否则选择R并将R向左移动一位。这样递归地选择下一步，直到只剩下一块披萨。递归基：当左右边界相遇时（即
L == R），说明只剩下一块披萨，直接返回这块披萨的美味值作为递归基。状态转移：在递归过程中，
dp[L][R]的值是通过比较选择左边界披萨和右边界披萨后，剩下披萨的最大美味值之和来确定的。
C++
#include<iostream>#include<vector>#include<algorithm>// 用于 std::max 函数using namespace std;intn;// 披萨的数量vector<int>a;// 每块披萨的美味值vector<vector<int>>dp;// 记忆化数组，用于存储已计算过的状态// 计算最大美味值的函数intallocation(intL,intR){if(dp[L][R]!=-1){returndp[L][R];// 如果已计算过，直接返回结果}if(a[L]>a[R]){L=(L+1)%n;// 左边披萨更美味，吃掉左边的}else{R=(R+n-1)%n;// 右边披萨更美味，吃掉右边的}if(L==R){dp[L][R]=a[L];// 只剩一块披萨时，返回其美味值}else{// 否则，递归计算剩下披萨的最大美味值，并更新记忆化数组dp[L][R]=max(a[L]+allocation((L+1)%n,R),a[R]+allocation(L,(R+n-1)%n));}returndp[L][R];// 返回当前状态下的最大美味值}intmain(){cin>>n;// 输入披萨的数量a.resize(n);// 调整数组大小以存储每块披萨的美味值for(inti=0;i<n;++i){cin>>a[i];// 输入每块披萨的美味值}dp.assign(n,vector<int>(n,-1));// 初始化记忆化数组intans=0;// 初始化最大美味值为 0for(inti=0;i<n;++i){// 更新最大美味值，allocation函数计算从当前披萨开始的最大美味值ans=max(ans,allocation((i+1)%n,(i+n-1)%n)+a[i]);}cout<<ans<<endl;// 输出最多能吃到的披萨的美味值return0;}Java
importjava.util.*;publicclassMain{staticintn;// 披萨的数量staticint[]a;// 每块披萨的美味值staticint[][]dp;// 记忆化数组，用于存储已计算过的状态publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);n=scanner.nextInt();// 输入披萨的数量a=newint[n];// 初始化存储每块披萨美味值的数组for(inti=0;i<n;i++){a[i]=scanner.nextInt();// 输入每块披萨的美味值}dp=newint[n][n];// 初始化记忆化数组，其维度为披萨数量的平方for(int[]row:dp){Arrays.fill(row,-1);// 初始化记忆化数组，将所有值设为-1，表示未计算}intans=0;// 初始化最大美味值为0// 遍历每块披萨，尝试以每块披萨作为起点计算最大美味值for(inti=0;i<n;i++){// 更新最大美味值，allocation函数计算从当前披萨开始的最大美味值ans=Math.max(ans,allocation((i+1)%n,(i+n-1)%n)+a[i]);}System.out.println(ans);// 输出最多能吃到的披萨的美味值总和}staticintallocation(intL,intR){// 如果当前状态已经计算过，则直接返回结果if(dp[L][R]!=-1){returndp[L][R];}// 根据贪心策略，选择当前美味值较大的披萨if(a[L]>a[R]){L=(L+1)%n;// 如果左边的披萨更美味，则吃掉左边的披萨}else{R=(R+n-1)%n;// 如果右边的披萨更美味，则吃掉右边的披萨}// 如果只剩下一块披萨，则直接返回这块披萨的美味值if(L==R){dp[L][R]=a[L];}else{// 否则，递归计算剩下披萨的最大美味值，并更新记忆化数组dp[L][R]=Math.max(a[L]+allocation((L+1)%n,R),a[R]+allocation(L,(R+n-1)%n));}returndp[L][R];// 返回当前状态下的最大美味值}}javaScript
constreadline=require('readline');// 创建 readline 接口constrl=readline.createInterface({input:process.stdin,output:process.stdout});letlines=[];// 用于存储输入行的数组letn;// 披萨的数量leta;// 每块披萨的美味值letdp;// 记忆化数组，用于存储已计算过的状态// 处理输入rl.on('line',(line)=>{lines.push(line);}).on('close',()=>{// 处理 lines 中的数据[n,...a]=lines.map(Number);// 第一行是披萨的数量，接下来的行是每块披萨的美味值a=a.slice(0,n);// 截取前 n 个数字作为美味值数组dp=Array.from({length:n},()=>Array(n).fill(-1));// 初始化记忆化数组letans=0;// 初始化最大美味值为 0for(leti=0;i<n;i++){ans=Math.max(ans,allocation((i+1)%n,(i+n-1)%n)+a[i]);}console.log(ans);// 输出最多能吃到的披萨的美味值总和});// 计算最大美味值的函数functionallocation(L,R){if(dp[L][R]!==-1){returndp[L][R];// 如果已计算过，直接返回结果}if(a[L]>a[R]){L=(L+1)%n;// 左边披萨更美味，吃掉左边的}else{R=(R+n-1)%n;// 右边披萨更美味，吃掉右边的}if(L==R){dp[L][R]=a[L];// 只剩一块披萨时，返回其美味值}else{dp[L][R]=Math.max(a[L]+allocation((L+1)%n,R),a[R]+allocation(L,(R+n-1)%n));}returndp[L][R];// 返回当前状态下的最大美味值}Python
# 用于读取输入的标准库importsys# 用于存储输入行的数组lines=[]# 读取标准输入forlineinsys.stdin:lines.append(line.strip())# 披萨的数量n=int(lines[0])# 每块披萨的美味值a=list(map(int,lines[1:1+n]))# 记忆化数组，用于存储已计算过的状态dp=[[-1for_inrange(n)]for_inrange(n)]# 计算最大美味值的函数defallocation(L,R):# 如果已计算过，直接返回结果ifdp[L][R]!=-1:returndp[L][R]# 根据美味值选择吃掉左边或右边的披萨ifa[L]>a[R]:L=(L+1)%nelse:R=(R+n-1)%n# 如果只剩一块披萨，返回其美味值ifL==R:dp[L][R]=a[L]else:dp[L][R]=max(a[L]+allocation((L+1)%n,R),a[R]+allocation(L,(R+n-1)%n))returndp[L][R]# 初始化最大美味值为 0ans=0# 计算并更新最大美味值foriinrange(n):ans=max(ans,allocation((i+1)%n,(i+n-1)%n)+a[i])# 输出最多能吃到的披萨的美味值总和print(ans)Go
packagemainimport("fmt""math")varnint// 披萨的数量vara[]int// 每块披萨的美味值vardp[][]int// 记忆化数组，用于存储已计算过的状态funcmain(){fmt.Scan(&n)// 输入披萨的数量a=make([]int,n)// 初始化存储每块披萨美味值的数组fori:=0;i<n;i++{fmt.Scan(&a[i])// 输入每块披萨的美味值}dp=make([][]int,n)// 初始化记忆化数组，其维度为披萨数量的平方fori:=rangedp{dp[i]=make([]int,n)forj:=rangedp[i]{dp[i][j]=-1// 初始化记忆化数组，将所有值设为-1，表示未计算}}ans:=0// 初始化最大美味值为0// 遍历每块披萨，尝试以每块披萨作为起点计算最大美味值fori:=0;i<n;i++{// 更新最大美味值，allocation函数计算从当前披萨开始的最大美味值ans=int(math.Max(float64(ans),float64(allocation((i+1)%n,(i+n-1)%n)+a[i])))}fmt.Println(ans)// 输出最多能吃到的披萨的美味值总和}funcallocation(L,Rint)int{// 如果当前状态已经计算过，则直接返回结果ifdp[L][R]!=-1{returndp[L][R]}// 根据贪心策略，选择当前美味值较大的披萨ifa[L]>a[R]{L=(L+1)%n// 如果左边的披萨更美味，则吃掉左边的披萨}else{R=(R+n-1)%n// 如果右边的披萨更美味，则吃掉右边的披萨}// 如果只剩下一块披萨，则直接返回这块披萨的美味值ifL==R{dp[L][R]=a[L]}else{// 否则，递归计算剩下披萨的最大美味值，并更新记忆化数组dp[L][R]=int(math.Max(float64(a[L]+allocation((L+1)%n,R)),float64(a[R]+allocation(L,(R+n-1)%n))))}returndp[L][R]// 返回当前状态下的最大美味值}C语言
#include<stdio.h>#include<stdlib.h>intmain(){intn;// 披萨的数量int*a;// 存储每块披萨美味值的数组int**dp;// 记忆化数组，用于存储已计算过的状态// 读取披萨的数量scanf("%d",&n);a=(int*)malloc(n*sizeof(int));// 读取每块披萨的美味值for(inti=0;i<n;i++){scanf("%d",&a[i]);}// 初始化记忆化数组dp=(int**)malloc(n*sizeof(int*));for(inti=0;i<n;i++){dp[i]=(int*)malloc(n*sizeof(int));for(intj=0;j<n;j++){dp[i][j]=-1;}}// 计算最大美味值的函数声明intallocation(int,int,int,int*,int**);intans=0;// 初始化最大美味值为 0for(inti=0;i<n;i++){ans=(ans>allocation((i+1)%n,(i+n-1)%n,n,a,dp)+a[i])?ans:allocation((i+1)%n,(i+n-1)%n,n,a,dp)+a[i];}// 输出最多能吃到的披萨的美味值总和printf("%d\n",ans);// 释放分配的内存for(inti=0;i<n;i++){free(dp[i]);}free(dp);free(a);return0;}// 计算最大美味值的函数intallocation(intL,intR,intn,int*a,int**dp){if(dp[L][R]!=-1){returndp[L][R];// 如果已计算过，直接返回结果}if(a[L]>a[R]){L=(L+1)%n;// 左边披萨更美味，吃掉左边的}else{R=(R+n-1)%n;// 右边披萨更美味，吃掉右边的}if(L==R){dp[L][R]=a[L];// 只剩一块披萨时，返回其美味值}else{dp[L][R]=(a[L]+allocation((L+1)%n,R,n,a,dp))>(a[R]+allocation(L,(R+n-1)%n,n,a,dp))?(a[L]+allocation((L+1)%n,R,n,a,dp)):(a[R]+allocation(L,(R+n-1)%n,n,a,dp));}returndp[L][R];// 返回当前状态下的最大美味值}完整用例
用例1
3 1 2 3用例2
5 1 2 3 4 5用例3
7 10 1 3 5 7 9 2用例4
9 8 7 6 5 4 3 2 1 9用例5
5 1 3 5 7 9用例6
3 5 5 5用例7
5 21412 100 200 300 400用例8
5 1 10 2 9 3用例9
7 2 4 6 8 10 12 14用例10
5 2 3 6 7 9
