1388.3n块披萨

链接：1388.3n块披萨
难度：Hard
标签：贪心、数组、动态规划、堆（优先队列）
简介：请你返回你可以获得的披萨大小总和的最大值。

题解 1 - cpp

• 编辑时间：2023-08-18
• 执行用时：28ms
• 内存消耗：14.1MB
• 编程语言：cpp
• 解法介绍：题目转化为3n个块中，选n个不相邻的块的最大和,dp[i][j]表示存在前i个块时，选取j个块的最大值。

class Solution {
public:
    int maxSizeSlices(vector<int>& slices) {
        int m = slices.size() / 3;
        auto check = [&](vector<int> nums) {
            int n = nums.size();
            vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    dp[i][j] = max(dp[i - 1][j], nums[i - 1]);
                    if (i >= 2) dp[i][j] = max(dp[i][j], dp[i - 2][j - 1] + nums[i - 1]);
                }
            }
            return dp[n][m];
        };
        return max(
            check(vector<int>(slices.begin() + 1, slices.end())),
            check(vector<int>(slices.begin(), slices.end() - 1))
        );
    }
};

题解 2 - python

• 编辑时间：2023-08-18
• 执行用时：444ms
• 内存消耗：16.19MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        m = len(slices) // 3
        def check(nums: List[int]) -> int:
            n = len(nums)
            dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
            for i in range(1, n+1):
                for j in range(1, m+1):
                    dp[i][j] = max(dp[i-1][j], nums[i-1])
                    if i >= 2:
                        dp[i][j] = max(dp[i][j], dp[i-2][j-1]+nums[i-1])
            return dp[n][m]
        return max(check(slices[1:]), check(slices[0:-1]))

题解 3 - rust

• 编辑时间：2023-08-18
• 执行用时：4ms
• 内存消耗：2.16MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn max_size_slices(slices: Vec<i32>) -> i32 {
        use std::cmp::max;
        let m = slices.len() / 3;
        let check = |nums: &[i32]| -> i32 {
            let n = nums.len();
            let mut dp = vec![vec![0; m + 1]; n + 1];
            for i in 1..=n {
                for j in 1..=m {
                    dp[i][j] = max(dp[i - 1][j], nums[i - 1]);
                    if i >= 2 {
                        dp[i][j] = max(dp[i][j], dp[i - 2][j - 1] + nums[i - 1])
                    }
                }
            }
            dp[n][m]
        };
        max(check(&slices[1..]), check(&slices[0..slices.len() - 1]))
    }
}