题目描述

        "吃货"和"馋嘴"两人到披萨店点了一份铁盘（圆形）披萨，并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。但是粗心的服务员将披萨切成了每块大小都完全不同的奇数块，且肉眼能分辨出大小。

       由于两人都想吃到最多的披萨，他们商量了一个他们认为公平的分法：从"吃货"开始，轮流取披萨。除了第一块披萨可以任意选取外，其他都必须从缺口开始选。

他俩选披萨的思路不同。"馋嘴"每次都会选最大块的披萨，而且"吃货"知道"馋嘴"的想法。

问题： 已知披萨小块的数量以及每块的大小，求"吃货"能分得的最大的披萨大小的总和。

解题思路

关键观察：

1. 圆形转线性：吃货第一步可以任意选择，这会将圆形披萨变成线性数组
2. 博弈策略：吃货知道馋嘴总是选最大的，可以利用这个信息制定最优策略
3. 动态规划：后续变成经典的区间博弈问题

算法步骤：

1. 枚举吃货第一块的所有可能选择
2. 对于每种选择，将剩余部分转化为线性博弈问题
3. 使用动态规划求解最优策略
4. 返回所有可能中的最大值

代码实现/C++

#include <iostream>
#include <vector>
#include <algorithm>class PizzaGame {
private:// 解决线性数组的博弈问题// player: 0=吃货, 1=馋嘴// 返回吃货能获得的最大收益int solveLinear(std::vector<int>& arr, int left, int right, int player,std::vector<std::vector<std::vector<int>>>& memo) {if (left > right) return 0;if (memo[left][right][player] != -1) {return memo[left][right][player];}int result;if (player == 0) { // 吃货的回合// 吃货选择能让自己最终收益最大的策略result = std::max(arr[left] + solveLinear(arr, left + 1, right, 1, memo),arr[right] + solveLinear(arr, left, right - 1, 1, memo));} else { // 馋嘴的回合// 馋嘴总是选最大的if (arr[left] >= arr[right]) {result = solveLinear(arr, left + 1, right, 0, memo);} else {result = solveLinear(arr, left, right - 1, 0, memo);}}return memo[left][right][player] = result;}public:int maxPizzaForChihuo(std::vector<int>& pizzaSizes) {int n = pizzaSizes.size();int maxResult = 0;// 枚举第一块披萨的选择for (int start = 0; start < n; start++) {int currentResult = pizzaSizes[start];if (n > 1) {// 构建剩余的线性数组std::vector<int> remaining;for (int i = 1; i < n; i++) {remaining.push_back(pizzaSizes[(start + i) % n]);}// 初始化记忆化数组int remainSize = remaining.size();std::vector<std::vector<std::vector<int>>> memo(remainSize, std::vector<std::vector<int>>(remainSize, std::vector<int>(2, -1)));// 解决剩余的线性博弈问题（馋嘴先手）currentResult += solveLinear(remaining, 0, remainSize - 1, 1, memo);}maxResult = std::max(maxResult, currentResult);}return maxResult;}
};

 测试用例

int main() {PizzaGame game;// 测试用例1: [1, 3, 7, 5, 2]std::vector<int> pizza1 = {1, 3, 7, 5, 2};std::cout << "测试1: [1,3,7,5,2] -> " << game.maxPizzaForChihuo(pizza1) << std::endl;// 输出: 11 (选择7开始，然后得到7+2+1+1=11)// 测试用例2: [2, 1, 3, 4, 6, 5, 7]  std::vector<int> pizza2 = {2, 1, 3, 4, 6, 5, 7};std::cout << "测试2: [2,1,3,4,6,5,7] -> " << game.maxPizzaForChihuo(pizza2) << std::endl;// 测试用例3: [10, 1, 2, 3, 4]std::vector<int> pizza3 = {10, 1, 2, 3, 4};std::cout << "测试3: [10,1,2,3,4] -> " << game.maxPizzaForChihuo(pizza3) << std::endl;// 输出: 14 (选择10开始，然后得到10+4=14)return 0;
}

 复杂度分析

• 时间复杂度： O(n³)

  • 外层枚举起点：O(n)
  • 内层动态规划：O(n²)
  • 总体：O(n³)

• 空间复杂度： O(n²)

  • 记忆化数组空间

解题要点

关键洞察：

1. 圆形特殊性：第一步可以任意选择，将圆形转化为线性问题
2. 对手策略：利用已知的对手贪心策略制定最优方案
3. 状态转移：区间DP的经典应用

易错点：

• 忘记考虑圆形数组的环形特性
• 没有正确处理博弈双方的不同策略
• 边界条件处理不当