上海专业网站推广公司,过期网站.,郑州最好的妇科医院排行,网站做链接的意义是什么文章目录 题目描述输入描述输出描述用例1解题思路Python3源码 题目描述 吃货和馋嘴两人到披萨店点了一份铁盘#xff08;圆形#xff09;披萨#xff0c;并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。但是粗心的服务员将披萨切成了每块大小都完全不… 文章目录 题目描述输入描述输出描述用例1解题思路Python3源码 题目描述 吃货和馋嘴两人到披萨店点了一份铁盘圆形披萨并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。但是粗心的服务员将披萨切成了每块大小都完全不同奇数块且肉眼能分辨出大小。 由于两人都想吃到最多的披萨他们商量了一个他们认为公平的分法从吃货开始轮流取披萨。除了第一块披萨可以任意选取外其他都必须从缺口开始选。 他俩选披萨的思路不同。馋嘴每次都会选最大块的披萨而且吃货知道馋嘴的想法。 已知披萨小块的数量以及每块的大小求吃货能分得的最大的披萨大小的总和。 输入描述
第 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 可能存在多种拿法以上只是其中一种。 解题思路
给定一个环形排列的披萨数组每块披萨有一个美味值需要计算出从任意位置开始能够获得的最大美味值总和。 环形处理由于披萨是环形排列的所以在选择披萨时需要考虑边界情况即当选择了最左边或最右边的披萨后如何循环到另一端。 动态规划使用一个二维数组 dp 作为记忆化存储其中 dp[L][R] 表示从左边界 L 到右边界 R 能够获得的最大美味值。如果 dp[L][R] 已经被计算过则直接返回该值。 递归计算定义一个递归函数来计算 dp[L][R]。如果 a[L]左边界的披萨美味值大于 a[R]右边界的披萨美味值则选择 L 并将L向右移动一位否则选择 R 并将 R 向左移动一位。这样递归地选择下一步直到只剩下一块披萨。 递归基当左右边界相遇时即 L R说明只剩下一块披萨直接返回这块披萨的美味值作为递归基。 状态转移在递归过程中dp[L][R] 的值是通过比较选择左边界披萨和右边界披萨后剩下披萨的最大美味值之和来确定的。
Python3源码
# 读取披萨的数量
n int(input())
# 读取每块披萨的美味值
arr [int(input()) for _ in range(n)]# 初始化 dp 数组dp为记忆化数组用于存储已计算过的状态
dp [[-1]*n for _ in range(n)]#计算最大披萨的函数
def cal_max(L,R):# 如果已计算过直接返回结果if dp[L][R] ! -1:return dp[L][R]# 根据美味值选择吃掉左边或右边的披萨if arr[L] arr[R]:L (L1)%nelse:R (Rn-1)%n# 如果只剩一块披萨返回其美味值if L R:dp[L][R] arr[L]else:dp[L][R] max(arr[L]cal_max((L1)%n,R),arr[R]cal_max(L,(Rn-1)%n))return dp[L][R]# 初始化最大美味值为 0
ans 0
# 计算并更新最大美味值
for i in range(n):ans max(ans,cal_max((i1)%n,(in-1)%n)arr[i])# 输出最多能吃到的披萨的美味值总和
print(ans)
