华为OD机试 - 分披萨 - 递归（Java 2024 D卷 200分）_华为od 分披萨

华为OD机试 2024D卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（D卷+C卷+A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

“吃货”和“馋嘴”两人到披萨店点了一份铁盘(圆形)披萨，并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。

但是粗心服务员将披萨切成了每块大小都完全不同奇数块，且肉眼能分辨出大小。

由于两人都想吃到最多的披萨，他们商量了一个他们认为公平的分法:从“吃货”开始，轮流取披萨。

除了第-块披萨可以任意选取以外，其他都必须从缺口开始选。 他俩选披萨的思路不同。

“馋嘴”每次都会选最大块的拨萨，而且“吃货”知道“馋嘴”的想法。

已知披萨小块的数量以及每块的大小，求“吃货”能分得的最大的披萨大小的总和。

二、输入描述

第1行为一个正整数奇数 N ，表示披萨小块数量。其中 3 ≤ N< 500

接下来的第 2 行到第 N+1 （共 N 行），每行为一个正整数，表示第i块披萨的大小， 1≤i≤N 。

披萨小块从某一块开始，按照一个方向次序顺序编号为 1 ~ N ,每块披萨的大小范围为[1,2147483647]。

三、输出描述

”吃货“能分得到的最大的披萨大小的总和。

四、测试用例

测试用例1：

1、输入

3
1
2
3

2、输出

4

3、说明

披萨被切成 3 块，大小分别为 1、2、3。
"吃货"最优策略是先选 3，然后 “馋嘴” 会选 2，最后 “吃货” 选 1。
因此，“吃货” 能获得的最大总和是 3 + 1 = 4。

测试用例2：

4、输入

7
10
20
30
40
50
60
70

5、输出

160

6、说明

披萨被切成 7 块，大小从 10 到 70。
“吃货” 的最优策略是选择 70、50、40，而 “馋嘴” 会选择 60、30、20。
“吃货” 获得的总和是 70 + 50 + 40 = 160。

五、解题思路

1. 读取披萨块的数量 n 和每块披萨的大小。
2. 使用哈希表存储中间结果以优化递归计算。
3. 递归计算：
   • 定义一个递归函数 f(l, r, t)，表示在 l 到 r 的范围内，在 t 次轮换中“吃货”可以获得的最大披萨总和。
   • 基于剩余次数 t 的不同，计算“吃货”可能的选择。
   • 递归模拟“吃货”和“馋嘴”的选取过程。
4. 结果计算：
   • 遍历所有可能的起始块，从每一块开始计算“吃货”能获得的最大总和。
   • 取所有计算结果的最大值。

虽然代码使用递归实现，但本质上是一个自顶向下的动态规划解法。每个子问题的解都可能被多次使用，我们通过缓存这些解来优化性能。

六、Java算法源码

public class OdTest01 {
    // 披萨块的数量
    private static int n;
    // 存储每块披萨的大小
    private static int[] pizza;
    // 用于记忆化搜索的缓存，键为"l,r,t"格式的字符串，值为对应状态下的最大得分
    private static Map<String, Integer> cache = new HashMap<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取披萨块的数量
        n = scanner.nextInt();
        pizza = new int[n];
        // 读取每块披萨的大小
        for (int i = 0; i < n; i++) {
            pizza[i] = scanner.nextInt();
        }

        int maxSum = 0;
        // 尝试从每一块披萨开始，找出能获得最大总和的起始位置
        for (int i = 0; i < n; i++) {
            // pizza[i] 是第一块选择的披萨，f(i-1, i+1, n-1) 计算剩余披萨的最优选择
            maxSum = Math.max(maxSum, pizza[i] + f(i - 1, i + 1, n - 1));
        }
        // 输出"吃货"能获得的最大披萨总和
        System.out.println(maxSum);
        scanner.close();
    }

    /**
     * 递归函数，计算在给定状态下"吃货"能获得的最大披萨总和
     *
     * @param l 左边界（不包括）
     * @param r 右边界（不包括）
     * @param t 剩余的选择次数
     * @return "吃货"在当前状态下能获得的最大披萨总和
     */
    private static int f(int l, int r, int t) {
        // 基本情况：如果剩余次数小于等于1，意味着这是"馋嘴"的最后一次选择，"吃货"无法再获得披萨
        if (t <= 1) {
            return 0;
        }

        // 处理循环边界，确保l和r在有效范围内
        l = (l + n) % n;
        r = r % n;

        // 检查缓存，如果之前计算过这个状态，直接返回缓存的结果
        String key = l + "," + r + "," + t;
        if (cache.containsKey(key)) {
            return cache.get(key);
        }

        // 模拟"馋嘴"的选择：总是选择较大的一块
        if (pizza[l] >= pizza[r]) {
            l = (l - 1 + n) % n;  // "馋嘴"选择了左边的披萨，左边界向左移动
        } else {
            r = (r + 1) % n;  // "馋嘴"选择了右边的披萨，右边界向右移动
        }

        // 计算"吃货"两种选择的结果：
        // 选择左边的披萨
        int s1 = pizza[l] + f((l - 1 + n) % n, r, t - 2);
        // 选择右边的披萨
        int s2 = pizza[r] + f(l, (r + 1) % n, t - 2);

        // 选择较大的结果
        int result = Math.max(s1, s2);
        // 将结果存入缓存
        cache.put(key, result);
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

七、效果展示

1、输入

5
10
10
10
10
10

2、输出

30

3、说明

披萨被切成 5 块，每块大小都是 10。
由于所有块大小相等，“吃货” 无论从哪里开始都可以获得 3 块披萨。
“吃货” 获得的总和是 10 + 10 + 10 = 30。