刷题笔记合集🔗

分披萨

问题描述

小兰和小基两人到披萨店点了一份铁盘（圆形）披萨，并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。但是粗心的服务员将披萨切成了每块大小都完全不同的奇数块，且肉眼能分辨出大小。

由于两人都想吃到最多的披萨，他们商量了一个他们认为公平的分法：从小兰开始，轮流取披萨。除了第一块披萨可以任意选取外，其他都必须从缺口开始选。

他俩选披萨的思路不同。小基每次都会选最大块的披萨，而且小兰知道小基的想法。

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

输入格式

第 行为一个正整数奇数 ，表示披萨小块数量。

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

披萨小块从某一块开始，按照一个方向次序顺序编号为 ~ 。

输出格式

小兰能分得到的最大的披萨大小的总和。

样例输入

5
8
2
10
5
7

样例输出

19

数据范围

• 
• 
• 每块披萨的大小范围为

题解

这道题描述了小兰和小基两人分披萨的场景，我们需要找出小兰能够获得的最大披萨总量。

题目给出了几个关键信息：

1. 披萨切成奇数块，每块大小各不相同
2. 小兰先选，两人轮流选择
3. 第一块可以任意选取，之后只能从缺口处（即已取块的两侧）选取
4. 小基每次都会选最大的块，这是一个确定的策略
5. 小兰知道小基的策略，想获得最大总量

首先分析问题的特性：由于披萨是奇数块，小兰先选，所以最后一块也会由小兰拿走。这是我们解题的一个关键点。

解决这个问题需要用到递归和记忆化搜索。思路如下：

1. 对于小兰的第一次选择，可以从N块中任选一块。此时选哪一块决定了后续的所有选择。
2. 一旦小兰做出选择，缺口就确定了，小基会从缺口两侧选择较大的一块。
3. 然后小兰再从新的缺口两侧选择，需要考虑选左边还是右边更有利。
4. 这个过程不断重复，直到所有披萨被分完。

由于需要考虑所有可能的初始选择，我们可以尝试每一种可能，找出最优解。对于每一种可能，我们使用递归来模拟整个选择过程。

但直接递归会导致大量重复计算，因为同样的缺口状态可能出现多次。因此我们使用记忆化搜索，即缓存已经计算过的状态结果，避免重复计算。

这个算法的时间复杂度是O(N³)，因为我们有N种初始选择，每种选择后有O(N²)个可能的缺口状态。空间复杂度是O(N²)，用于存储缓存。对于N < 500的约束，这个复杂度是可以接受的。

在具体实现中，我们可以用一个二维数组cache[l][r]来存储当缺口位置为l和r时，小兰能获得的最大披萨总量。这样，我们就能避免重复计算，提高效率。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 输入获取
n = int(input())  # 披萨数量（奇数个）

pizza = []  # n个披萨的大小（各不相同）
for _ in range(n):
    pizza.append(int(input()))

# 缓存表
cache = [[-1] * n for _ in range(n)]

# 处理索引超出边界情况，实现环形效果
def wrap(idx):
    if idx < 0:
        return n - 1
    elif idx >= n:
        return 0
    return idx

def calc(l, r):
    # 如果已经计算过该状态，直接返回缓存结果
    if cache[l][r] != -1:
        return cache[l][r]
    
    # 小基会选择缺口两侧中较大的一块
    if pizza[l] > pizza[r]:
        next_l = wrap(l - 1)  # 小基选了左边，更新左侧缺口
        next_r = r
    else:
        next_l = l
        next_r = wrap(r + 1)  # 小基选了右边，更新右侧缺口
    
    # 如果只剩一块披萨，小兰获得它
    if next_l == next_r:
        cache[l][r] = pizza[next_l]
        return pizza[next_l]
    
    # 小兰有两种选择，取左边或右边，选择能获得最大总量的方案
    left_choice = calc(wrap(next_l - 1), next_r) + pizza[next_l]
    right_choice = calc(next_l, wrap(next_r + 1)) + pizza[next_r]
    cache[l][r] = max(left_choice, right_choice)
    
    return cache[l][r]

# 主函数
def solve():
    max_sum = 0
    
    # 尝试小兰第一次选择每一块披萨
    for i in range(n):
        # i是小兰选择