分披萨 - 华为OD统一考试(C卷)

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

alt

题目描述

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

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

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

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

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

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

输入描述

第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 < n; i++) p[i] = in.nextInt();

        Solution solution = new Solution();

        System.out.println(solution.solve(p, n));
    }
}

class Solution {
    int n;
    int[] p;
    long[][] cache;

    /**
     * @param l, r: 可以选择的两端索引下标
     * @param t: 剩余的披萨块数
     * @return: 返回 “吃货” 最优选择时可以分到的披萨总和
     */
    private long getMaxSum(int l, int r, int t) {
        if (t <= 1) return 0L;
        l = (l + n) % n;
        r = r % n;

        // “馋嘴” 选择最大的一块
        if (p[l] >= 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 < n; i++) {
            maxsum = Math.max(maxsum, p[i] + getMaxSum(i - 1, i + 1, n - 1));
        }

        return maxsum;
    }
}

Python

def get_max_sum(l, r, t):
    """
    :param l: 左边界
    :param r: 右边界
    :param t: 剩余次数
    :return: 返回 “吃货” 最优选择时可以分到的披萨总和
    """
    global n, p, cache
    if t <= 1:
        return 0

    l, r = (l + n) % n, r % n

    # “馋嘴”选择最大的一块
    if p[l] >= p[r]:
        l = (l - 1 + n) % n
    else:
        r = (r + 1) % n

    if cache[l][r] != -1:
        return cache[l][r]

    # “吃货”选择 p[l]
    s1 = p[l] + get_max_sum(l - 1, r, t - 2)

    # “吃货”选择 p[r]
    s2 = p[r] + get_max_sum(l, r + 1, t - 2)

    # “吃货”选择最大的一块，并返回结果
    cache[l][r] = max(s1, s2)
    return cache[l][r]


if __name__ == "__main__":
    n = int(input())
    p = list(int(input()) for _ in range(n))
    cache = [[-1] * n for _ in range(n)]

    # “吃货”尝试每种选择，然后取结果最大的值
    maxsum = max(p[i] + get_max_sum(i - 1, i + 1, n - 1) for i in range(n))

    print(maxsum)

C++

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> p;
vector<vector<long long>> cache;


/**
 * 
 * @param l, r: 可以选择的两端索引下标
 * @param t: 剩余的披萨块数
 * 
 * @return: 返回 “吃货” 最优选择时可以分到的披萨总和
*/
long long get_max_sum(int l, int r, int t){
    if(t <= 1) return 0LL;
    l = (l + n) % n;
    r = r % n;

    // “馋嘴” 选择最大的一块
    if(p[l] >= 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<long long>(n, -1));

    for(int i = 0; i < n; i++) cin >> p[i];

    long long maxsum = 0;

    //  “吃货” 尝试每种选择，然后取结果最大的值
    for(int i = 0; i < n; i++){
        maxsum = max(maxsum, p[i] + get_max_sum(i - 1, i + 1, n - 1));
    }

    cout << maxsum << endl;

    return 0;
}