阅读量:2
题目描述
“吃货”和“馋嘴”两人到披萨店点了一份铁盘(圆形)披萨，并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。
但是粗心服务员将披萨切成了每块大小都完全不同奇数块，且肉眼能分辨出大小。
由于两人都想吃到最多的披萨，他们商量了一个他们认为公平的分法:从“吃货”开始，轮流取披萨。
除了第-块披萨可以任意选取以外，其他都必须从缺口开始选。 他俩选披萨的思路不同。
“馋嘴”每次都会选最大块的拨萨，而且“吃货”知道“馋嘴”的想法。
已知披萨小块的数量以及每块的大小，求“吃货”能分得的最大的披萨大小的总和。
输入描述
第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 可能存在多种拿法，以上只是其中一种。 解题思路
解题思路
- 记忆化搜索：定义一个递归函数
f(l, r, t)来表示从区间[l, r]里，“吃货”能分得的最大披萨大小的总和。这里l和r分别表示区间的左边界和右边界，t表示剩余的次数。- 贪心选择：每次“馋嘴”都会选择当前区间内最大的披萨块，这会影响到下一步“吃货”的选择。因此，我们需要在“吃货”选择之前模拟“馋嘴”的贪心选择，以确保“吃货”能得到最大总和。
- 递归处理：递归地缩小问题规模，通过模拟“吃货”在每一步的选择，并记录下最优结果。
代码描述
- 输入处理：读取输入的披萨块数量
n和每块披萨的大小。- 缓存优化：使用
functools.cache来缓存递归结果，避免重复计算。- 递归函数
f：
- 参数：
l为左边界，r为右边界，t为剩余次数。- 基本情况：如果剩余次数
t小于等于1，则返回0。- 贪心选择：模拟“馋嘴”选择当前区间内的最大披萨块，更新
l或r。- 动态规划选择：计算“吃货”选择左边界
l或右边界r时的最大总和，并返回其中较大的值。- 主逻辑：通过遍历每块披萨，计算“吃货”从该块披萨开始能得到的最大总和。
Python
from functools import cache n = int(input()) pizza = list(int(input()) for _ in range(n)) @cache def f(l: int, r: int, t: int) -> int: """ :param l: 左边界 :param r: 右边界 :param t: 剩余次数 :return: 返回 “吃货” 最优选择时可以分到的披萨总和 """ global n, pizza if t <= 1: return 0 l, r = (l + n) % n, r % n # “馋嘴”选择最大的一块 if pizza[l] >= pizza[r]: l = (l - 1 + n) % n else: r = (r + 1) % n # “吃货”选择 pizza[l] s1 = pizza[l] + f(l - 1, r, t - 2) # “吃货”选择 pizza[r] s2 = pizza[r] + f(l, r + 1, t - 2) return max(s1, s2) print(max(pizza[i] + f(i - 1, i + 1, n - 1) for i in range(n))) @cache 的作用和使用
作用
- 性能优化：通过缓存函数的返回值，避免对相同输入的函数进行多次计算。
- 简洁代码：使用装饰器的方式可以使代码更加简洁和易读。
使用方法
- 在函数定义的上方添加
@cache装饰器即可。
示例方法
from functools import cache @cache def fibonacci(n): if n < 2: return n return fibonacci(n - 1) + fibonacci(n - 2) print(fibonacci(50)) 在上述例子中，
fibonacci函数使用了@cache装饰器。当计算fibonacci(50)时，fibonacci函数会缓存所有中间结果，避免了大量重复计算，使得计算速度显著提升。
@cache 与 @lru_cache 的区别
@cache：- 缓存所有的函数调用结果，直到程序结束或缓存被手动清除。
- 不限制缓存大小，可能会导致内存占用较大。
@lru_cache：- Least Recently Used (LRU) 缓存，会限制缓存大小，默认最大缓存大小为 128，可以通过参数调整。
- 当缓存满了，会自动清除最久未使用的缓存项，以保持缓存大小在设定范围内。
示例代码
from functools import lru_cache @lru_cache(maxsize=128) def fibonacci(n): if n < 2: return n return fibonacci(n - 1) + fibonacci(n - 2) print(fibonacci(50)) 相关练习题
| 题号 | 题目 | 难易 |
|---|---|---|
| LeetCode 486 | 486. 预测赢家 | 中等 |
| LeetCode 464 | 464. 我能赢吗 | 中等 |
2024华为OD机试（C卷+D卷）最新题库【超值优惠】Java/Python/C++合集
🙏整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
