C++刷leetcode（1388. 3n 块披萨****）【动态规划】
题目描述：给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：
你挑选 任意 一块披萨。
Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
重复上述过程直到没有披萨剩下。
每一块披萨的大小按顺时针方向由循环数组 slices 表示。
请你返回你可以获得的披萨大小总和的最大值。
示例 1：
输入：slices =
输出：10
解释：选择大小为 4 的披萨，Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。然后你选择大小为 6 的披萨，Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。你获得的披萨总大小为 4 + 6 = 10 。
示例 2：
输入：slices =
输出：16
解释：两轮都选大小为 8 的披萨。如果你选择大小为 9 的披萨，你的朋友们就会选择大小为 8 的披萨，这种情况下你的总和不是最大的。
示例 3：
输入：slices =
输出：21
示例 4：
输入：slices =
输出：3
提示：
1 <= slices.length <= 500
slices.length % 3 == 0
1 <= slices <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pizza-with-3n-slices
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int calculate(const vector<int>& slices) {
int n = slices.size();
int choose = (n + 1) / 3;
vector<vector<int> > dp(n + 1, vector<int>(choose + 1));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= choose; ++j) {
dp = max(dp, (i - 2 >= 0 ? dp : 0) + slices);
}
}
return dp;
}
int maxSizeSlices(vector<int>& slices) {
vector<int> v1(slices.begin() + 1, slices.end());
vector<int> v2(slices.begin(), slices.end() - 1);
int ans1 = calculate(v1);
int ans2 = calculate(v2);
return max(ans1, ans2);
}
};
参考链接：https://leetcode-cn.com/problems/pizza-with-3n-slices/solution/3n-kuai-pi-sa-by-leetcode-solution/
注意事项：
1.又是打家劫舍系列变型题。 {:10_255:}
页:
[1]