5351.3n 块披萨 (Hard)*

题目描述*

给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：

你挑选任意一块披萨。 Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。 Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。重复上述过程直到没有披萨剩下。每一块披萨的大小按顺时针方向由循环数组 slices 表示。

请你返回你可以获得的披萨大小总和的最大值。

提示*

1 <= slices.length <= 500, slices.length % 3 == 0, 1 <= slices[i] <= 1000

代码*

现在基本看到题一瞅就是 dp，一写就不会。

显然最后选的都是不相邻的，所以可以转换成求不相邻子数组的最大和。同为首尾也算是相邻，所以这个题可以先去掉首或尾元素，算两边取大的。

dp[i][j] 表示已经最多取了 i + 1 块，且取了第 j 块元素的最大值。仅用了上一层，二维可以压缩成一维的。

二维 dp一维 dp

class Solution {
private:
    int helper(vector<int>& slices) {
        int len = slices.size();
        if(len == 0) {
            return 0;
        }
        vector<vector<int>> dp(len / 3 + 1, vector<int>(len, 0));
        dp[0] = slices;
        for(int i = 1; i < len / 3 + 1; i++) {
            int preMax = 0;
            for(int j = 0; j < len; j++) {
                if(j >= 2 && dp[i - 1][j - 2] > preMax) {
                    preMax = dp[i - 1][j - 2];
                }
                dp[i][j] = slices[j] + preMax;
            }
        }
        return *max_element(dp.back().begin(), dp.back().end());
    }
public:
    int maxSizeSlices(vector<int>& slices) {
        if(slices.size() == 0) {
            return 0;
        }
        vector<int> v1(slices.begin() + 1, slices.end());
        vector<int> v2(slices.begin(), prev(slices.end()));
        return max(helper(v1), helper(v2));
    }
};

class Solution {
private:
    int helper(vector<int>& slices) {
        int len = slices.size();
        if(len == 0) {
            return 0;
        }
        vector<int> pre(slices);
        vector<int> dp(len, 0);
        for(int i = 1; i < len / 3 + 1; i++) {
            int preMax = 0;
            for(int j = 0; j < len; j++) {
                if(j >= 2 && pre[j - 2] > preMax) {
                    preMax = pre[j - 2];
                }
                dp[j] = slices[j] + preMax;
            }
            swap(pre, dp);
        }
        return *max_element(pre.begin(), pre.end());
    }
public:
    int maxSizeSlices(vector<int>& slices) {
        if(slices.size() == 0) {
            return 0;
        }
        vector<int> v1(slices.begin() + 1, slices.end());
        vector<int> v2(slices.begin(), prev(slices.end()));
        return max(helper(v1), helper(v2));
    }
};

最后更新: July 23, 2022