↓Skip to main content
  1. Posts/

LeetCode-1388 3n 块披萨

·1 min·
Table of Contents

LeetCode-1388 3n 块披萨 #

Solution 1 #

取完某块披萨, 相邻的披萨一定不能再取了, 因此取的元素至少满足不能相邻这一点. 实际上, 从 $3n$ 个元素中取出 $n$ 个不相邻的元素一定能够对应某种披萨的取法. 详细的证明可以参考力扣官方题解. 知晓这一点后利用动态规划即可. 代码如下:

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