每日一算：华为-批萨分配问题

题目描述

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

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

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

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

解题思路

关键观察：

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

算法步骤：

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

代码实现/C++

#include #include #include class PizzaGame {private: // 解决线性数组的博弈问题 // player: 0=吃货, 1=馋嘴 // 返回吃货能获得的最大收益 int solveLinear(std::vector& arr, int left, int right, int player,  std::vector<std::vector<std::vector>>& 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& pizzaSizes) { int n = pizzaSizes.size(); int maxResult = 0; // 枚举第一块披萨的选择 for (int start = 0; start  1) { // 构建剩余的线性数组 std::vector 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>> memo(  remainSize,  std::vector<std::vector>(remainSize, std::vector(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 pizza1 = {1, 3, 7, 5, 2}; std::cout < \"  << game.maxPizzaForChihuo(pizza1) << std::endl; // 输出: 11 (选择7开始，然后得到7+2+1+1=11) // 测试用例2: [2, 1, 3, 4, 6, 5, 7] std::vector pizza2 = {2, 1, 3, 4, 6, 5, 7}; std::cout < \"  << game.maxPizzaForChihuo(pizza2) << std::endl; // 测试用例3: [10, 1, 2, 3, 4] std::vector pizza3 = {10, 1, 2, 3, 4}; std::cout < \"  << 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的经典应用

易错点：

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