P3481. 分披萨

解题思路

如何处理环形数组？

Q：这题所提供的数组要求是环形的，怎么处理？ A：将数组复制一次，拼接在原数组后面。因此，到时候取 a[0...n-1]、a[1...n]、a[2...n+1]、…… 中的最优一个解即可。

动态规划三部曲

dp 数组的含义是什么？

dp 数组是一个长度为 (n+n) * (n+n) 的二维列表，f[i][j] 表示吃货将 a[i...j] 中所有的披萨吃完后，吃货得到的最多披萨量。需要保证披萨的数量是奇数块，即 (j-i+1) % 2 = 1。

动态转移方程是什么？

需要求解 f[i][j]。吃货有两种选择：

• 选择 `a[i]`（剩下 a[i+1...j]）：
• 如果馋嘴觉得 a[i+1] > a[j]，只剩下 a[i+2...j]，对应 f[i+2][j]，则 f[i][j] = f[i+2][j] + a[i]；
• 如果馋嘴觉得 a[i+1] < a[j]，只剩下 a[i+1...j-1]，对应 f[i+1][j-1]，则 f[i][j] = f[i+1][j-1] + a[i]。

• 选择 `a[j]`（剩下 a[i...j-1]）：
• 如果馋嘴觉得 a[i] > a[j-1]，只剩下 a[i+1...j-1]，对应 f[i+1][j-1]，则 f[i][j] = f[i+1][j-1] + a[j]；
• 如果馋嘴觉得 a[i] < a[j-1]，只剩下 a[i...j-2]，对应 f[i][j-2]，则 f[i][j] = f[i][j-2] + a[j]。

对应的代码实现如下：

dp 数组如何初始化？

一开始，如果只有一块披萨 a[i...i] 的话，吃货吃下 a[i]，因此有 f[i][i] = a[i]。

初始化代码如下：

最终求解

最终求解出 f 数组，由于我们给定的是环形披萨，因此全局的最大值为 max(f[0][n-1], f[1][n], ..., f[n-1][n+n-2])。

复杂度分析 设 n 为披萨的块数。为了处理环形结构，代码把数组复制一倍拼接，实际参与计算的规模是 2n。

• 时间：主体是双重循环。外层 k 从 3 开始、每次加 2 枚举区间长度，约有 n/2 种取值；内层 i 枚举区间起点，最多 2n 个；每个状态 f[i][j] 只做常数次比较和取最大值。因此 dp 部分为 O(n^2)。最后在 n 个环形起点对应的 f[i][i+n-1] 中取最大值只需 O(n)，不影响量级。总时间复杂度为 O(n^2)。
• 空间：dp 表 f 是 (2n) × (2n) 的二维数组，空间复杂度为 O(n^2)，这是本算法的主要开销。C++ 版本用 long long 存储 f，防止多块披萨大小累加后超出 int 范围。