Pizza With 3n Slices trong C++

Pizza 3n miếng xếp tròn. Bạn chọn 1 miếng, Amal lấy miếng kế tiếp chống chiều kim đồng hồ, Bimal lấy miếng theo chiều kim đồng hồ. Lặp lại. Tối đa hóa tổng kích thước miếng bạn nhận được.

Ví dụ: [9,8,6,1,1,8] → chọn 8 mỗi lượt → tổng = 16.

Giải thuật (DP trên đường tròn)

Chuyển thành bài toán: chọn n/3 phần tử không kề nhau từ mảng vòng. Tách 2 trường hợp: không chọn phần tử 0, hoặc chọn phần tử 0 (thì không chọn phần tử 1 và n-1). DP[i][j][0/1] = max sum chọn j phần tử từ i phần tử đầu, 0/1 = có chọn phần tử cuối không.

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int solve(vector<int> v, int m) {
        int n = v.size();
        vector<vector<int>> dp1(n+1, vector<int>(m+1, 0));
        vector<vector<int>> dp2(n+1, vector<int>(m+1, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= m; j++) {
                int x = v[i];
                if (j < m) dp2[i+1][j+1] = max(dp2[i+1][j+1], dp1[i][j] + x);
                dp1[i+1][j] = max({dp1[i+1][j], dp2[i][j], dp1[i][j]});
            }
        }
        return max(dp1[n][m], dp2[n][m]);
    }
public:
    int maxSizeSlices(vector<int>& slices) {
        int n = slices.size();
        int pick = n / 3;
        // Trường hợp 1: không chọn slices[0]
        int ans1 = solve(vector<int>(slices.begin() + 1, slices.end()), pick);
        // Trường hợp 2: chọn slices[0], không chọn slices[1] và slices[n-1]
        int ans2 = slices[0] + solve(vector<int>(slices.begin() + 2, slices.end() - 1), pick - 1);
        return max(ans1, ans2);
    }
};

int main() {
    Solution ob;
    vector<int> v = {9,8,6,1,1,8};
    cout << ob.maxSizeSlices(v); // 16
    return 0;
}

Đầu vào / Đầu ra

Input: {9,8,6,1,1,8}
Output: 16