题目描述
“吃货”和“馋嘴”两人到披萨店点了一份铁盘(圆形)披萨，并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。
但是粗心服务员将披萨切成了每块大小都完全不同奇数块，且肉眼能分辨出大小。
由于两人都想吃到最多的披萨，他们商量了一个他们认为公平的分法:从“吃货”开始，轮流取披萨。
除了第-块披萨可以任意选取以外，其他都必须从缺口开始选。 他俩选披萨的思路不同。
“馋嘴”每次都会选最大块的拨萨，而且“吃货”知道“馋嘴”的想法。
已知披萨小块的数量以及每块的大小，求“吃货”能分得的最大的披萨大小的总和。
输入描述
第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
可能存在多种拿法，以上只是其中一种。
解题思路
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))
@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))
相关练习题
🙏整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏