C++刷leetcode（1388. 3n 块披萨****）【动态规划】

糖逗

题目描述：

1. 给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：
   
2. 
   
3. 你挑选 任意 一块披萨。
   
4. Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
   
5. Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
   
6. 重复上述过程直到没有披萨剩下。
   
7. 每一块披萨的大小按顺时针方向由循环数组 slices 表示。
   
8. 
   
9. 请你返回你可以获得的披萨大小总和的最大值。
   
10. 
    
11.  
    
12. 
    
13. 示例 1：
    
14. 
    
15. 
    
16. 
    
17. 输入：slices = [1,2,3,4,5,6]
    
18. 输出：10
    
19. 解释：选择大小为 4 的披萨，Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。然后你选择大小为 6 的披萨，Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。你获得的披萨总大小为 4 + 6 = 10 。
    
20. 示例 2：
    
21. 
    
22. 
    
23. 
    
24. 输入：slices = [8,9,8,6,1,1]
    
25. 输出：16
    
26. 解释：两轮都选大小为 8 的披萨。如果你选择大小为 9 的披萨，你的朋友们就会选择大小为 8 的披萨，这种情况下你的总和不是最大的。
    
27. 示例 3：
    
28. 
    
29. 输入：slices = [4,1,2,5,8,3,1,9,7]
    
30. 输出：21
    
31. 示例 4：
    
32. 
    
33. 输入：slices = [3,1,2]
    
34. 输出：3
    
35.  
    
36. 
    
37. 提示：
    
38. 
    
39. 1 <= slices.length <= 500
    
40. slices.length % 3 == 0
    
41. 1 <= slices[i] <= 1000
    
42. 
    
43. 来源：力扣（LeetCode）
    
44. 链接：https://leetcode-cn.com/problems/pizza-with-3n-slices
    
45. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int calculate(const vector<int>& slices) {
   
4.         int n = slices.size();
   
5.         int choose = (n + 1) / 3;
   
6.         vector<vector<int> > dp(n + 1, vector<int>(choose + 1));
   
7.         for (int i = 1; i <= n; ++i) {
   
8.             for (int j = 1; j <= choose; ++j) {
   
9.                 dp[i][j] = max(dp[i - 1][j], (i - 2 >= 0 ? dp[i - 2][j - 1] : 0) + slices[i - 1]);
   
10.             }
    
11.         }
    
12.         return dp[n][choose];
    
13.     }
    
14. 
    
15.     int maxSizeSlices(vector<int>& slices) {
    
16.         vector<int> v1(slices.begin() + 1, slices.end());
    
17.         vector<int> v2(slices.begin(), slices.end() - 1);
    
18.         int ans1 = calculate(v1);
    
19.         int ans2 = calculate(v2);
    
20.         return max(ans1, ans2);
    
21.     }
    
22. };

复制代码

参考链接：https://leetcode-cn.com/problems ... -leetcode-solution/

注意事项：
1.又是打家劫舍系列变型题。

糖逗