3n 块披萨

题目

1388. 3n 块披萨

---

给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：

• 你挑选 任意 一块披萨。
• Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
• Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
• 重复上述过程直到没有披萨剩下。

每一块披萨的大小按顺时针方向由循环数组 slices 表示。

请你返回你可以获得的披萨大小总和的最大值。

示例 1：

输入：slices = [1,2,3,4,5,6]
输出：10
解释：选择大小为 4 的披萨，Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。然后你选择大小为 6 的披萨，Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。你获得的披萨总大小为 4 + 6 = 10 。

示例 2：

输入：slices = [8,9,8,6,1,1]
输出：16
解释：两轮都选大小为 8 的披萨。如果你选择大小为 9 的披萨，你的朋友们就会选择大小为 8 的披萨，这种情况下你的总和不是最大的。

提示：

• 1 <= slices.length <= 500
• slices.length % 3 == 0
• 1 <= slices[i] <= 1000

题解

方法一：

思路

读错题，每次是可以任选的，但是每次我都是基于上次选择左右，变成了博弈问题。

问题需要转化，我们选的披萨一定是不相邻的，所有不相邻的披萨的选择方式可以是我们所选的答案

可以用f(i, j)表示前i个数中选j个不同数的最大总和。

现在对于i是否选择分析状态转移。

当选择i时，在前i-2个数中选则j个
f(i, j) = f(i-2, j-1)+1

当不选择i时，就是前i-1个数中选择j个。
f(i, j) = f(i-1, j)

选择最大值作为转移
f(i,j) = max( f(i-2,j-1)+1, f(i-1,j) )

由于第一个和最后一个数是相邻的，我们需要去掉第一个数进行一次dp，去掉最后一个数进行dp，取最大值即可。

代码

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        n = len(slices)
        def DP(s:List[int]) -> int:
            sz = len(s)
            f = [[0]*sz for _ in range(sz)]
            f[0][1], f[1][1] = s[0], max(s[0], s[1])
            for i in range(2, sz):
                for j in range(1, n//3+1):
                    f[i][j] = max(f[i-1][j], f[i-2][j-1]+s[i])
            return f[sz-1][n//3]
        return max(DP(slices[1:]), DP(slices[:-1]))