| 分披萨 | 您所在的位置：网站首页 › 初一披萨题 › 分披萨 |
分披萨
|
本文主要是介绍分披萨 - 华为OD统一考试(C卷)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！ OD统一考试（C卷） 分值： 100分 题解： Java / Python / C++
“吃货”和“馋嘴”两人到披萨店点了一份铁盘(圆形)披萨，并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。 但是粗心服务员将披萨切成了每块大小都完全不同奇数块，且肉眼能分辨出大小。 由于两人都想吃到最多的披萨，他们商量了一个他们认为公平的分法:从“吃货”开始，轮流取披萨。 除了第-块披萨可以任意选取以外，其他都必须从缺口开始选。 他俩选披萨的思路不同。 “馋嘴”每次都会选最大块的拨萨，而且“吃货”知道“馋嘴”的想法。 已知披萨小块的数量以及每块的大小，求“吃货”能分得的最大的披萨大小的总和。 输入描述第1行为一个正整数奇数 N ，表示披萨小块数量。其中 3 ≤ N< 500 接下来的第 2 行到第 N+1 （共 N 行），每行为一个正整数，表示第i块披萨的大小， 1≤i≤N 。 披萨小块从某一块开始，按照一个方向次序顺序编号为 1 ~ N ,每块披萨的大小范围为[1,2147483647]。 输出描述”吃货“能分得到的最大的披萨大小的总和。 示例1 输入： 5 8 2 10 5 7输出： 19说明： 此例子中，有 5 块披萨。每块大小依次为 8 、2 、10 、5 、7。 按照如下顺序拿披萨，可以使”吃货拿到最多披萨: “吃货”拿大小为 10 的披萨 “馋嘴”拿大小为5的披萨 “吃货”拿大小为7 的披萨 “馋嘴”拿大小为 8 的披萨 ”吃货“拿大小为2 的披萨 至此，披萨瓜分完毕，”吃货“拿到的披萨总大小为 10+7+2=19 可能存在多种拿法，以上只是其中一种。 题解解题思路： 记忆化搜索算法，计算“吃货”在每一轮中的最佳选择。使用二维缓存数组 cache 来存储中间结果，避免重复计算。 代码描述： 定义 get_max_sum 函数，表示在给定可选的左右边界索引和剩余披萨块数，吃货能分到的最大披萨总和。在 get_max_sum 函数中，首先对左右边界进行调整（避免数组越界），“馋嘴”选择最大的一块。使用递归计算（ “吃货”）两种情况下的最大总和：选择左边界块和选择右边界块。返回最优解并将结果缓存到 cache 中，避免重复计算。在主函数中，尝试每种选择，然后取结果最大的值。 Java import java.util.Arrays; import java.util.Scanner; /*** @author code5bug*/ public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int[] p = new int[n];for (int i = 0; i if (t = p[r]) {l = (l - 1 + n) % n;} else {r = (r + 1) % n;}if (cache[l][r] != -1) return cache[l][r];long s1 = p[l] + getMaxSum(l - 1, r, t - 2); // “吃货” 选择 p[l]long s2 = p[r] + getMaxSum(l, r + 1, t - 2); // “吃货” 选择 p[r]// “吃货” 选择最有利的，并返回结果return cache[l][r] = Math.max(s1, s2);}public long solve(int[] p, int n) {this.p = p;this.n = n;this.cache = new long[n][n];Arrays.stream(cache).forEach(row -> Arrays.fill(row, -1));long maxsum = 0;for (int i = 0; i if(t = p[r]){l = (l - 1 + n) % n;}else{r = (r + 1) % n;}if(cache[l][r] != -1) return cache[l][r];// “吃货” 选择 p[l]long long s1 = p[l] + get_max_sum(l - 1, r, t - 2);// “吃货” 选择 p[r]long long s2 = p[r] + get_max_sum(l, r + 1, t - 2);// “吃货” 选择最大的一块，并返回结果return cache[l][r] = max(s1, s2); }int main(){cin >> n;p.resize(n);cache.resize(n, vector(n, -1));for(int i = 0; i > p[i];long long maxsum = 0;// “吃货” 尝试每种选择，然后取结果最大的值for(int i = 0; i |
【本文地址】
公司简介
联系我们