Pizza With 3n Slices: เลือกชิ้นพิซซ่าผลรวมสูงสุดใน C++

ปัญหา

พิซซ่า 3n ชิ้นเรียงเป็นวงกลม คุณและเพื่อน 2 คน สลับกันหยิบ: 1. คุณหยิบชิ้นใดก็ได้ 2. ออมลหยิบชิ้นข้างหน้า (Counter-clockwise) 3. บีمالหยิบชิ้นข้างหลัง (Clockwise) ซ้ำจนหมด หาผลรวมขนาดชิ้นที่คุณได้สูงสุด

ตัวอย่าง: [9,8,6,1,1,8] (n=2) → คำตอบ: 16 (หยิบ 8, 8)

ข้อสังเกตสำคัญ

เนื่องจากเพื่อนหยิบชิ้นติดกันทั้งสองข้าง การที่คุณหยิบชิ้น i จะ กำจัดชิ้น i-1 และ i+1 ด้วย ปัญหากลายเป็น: เลือก n ชิ้นจาก 3n ชิ้นวงกลม โดยไม่ให้เลือกติดกัน

แปลงเป็น Linear Array

วงกลม → พิจารณา 2 กรณี (ไม่ให้เลือกทั้ง first และ last พร้อมกัน):

1. ไม่เลือกชิ้นแรก (index 0): โจทย์กลายเป็นเลือก n ชิ้นจาก 3n-1 ชิ้น (index 1..3n-1) แบบ Linear
2. เลือกชิ้นแรก: ต้องไม่เลือกชิ้นสุดท้ายและชิ้นที่ 2 → เลือก n-1 ชิ้นจาก index 2..3n-2

DP บน Linear Array

dp[i][j][taken] = คะแนนสูงสุดจากชิ้นแรก i ชิ้น เลือก j ชิ้น โดยชิ้นที่ i ถูกเลือกหรือไม่ (taken)

Transition

// ไม่เลือกชิ้น i
dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][0], dp[i][j][1])

// เลือกชิ้น i (ต้องไม่ได้เลือกชิ้น i-1)
dp[i+1][j+1][1] = max(dp[i+1][j+1][1], dp[i][j][0] + v[i])

โค้ด C++

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

class Solution {
    int solve(vector<int> v, int m) {  // m = จำนวนชิ้นที่ต้องเลือก
        int n = v.size();
        vector<vector<int>> dp0(n+1, vector<int>(m+1, 0));  // not taken
        vector<vector<int>> dp1(n+1, vector<int>(m+1, 0));  // taken
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= m; j++) {
                // ไม่เลือก v[i]
                dp0[i+1][j] = max({dp0[i+1][j], dp0[i][j], dp1[i][j]});
                // เลือก v[i]
                if (j < m) {
                    dp1[i+1][j+1] = max(dp1[i+1][j+1], dp0[i][j] + v[i]);
                }
            }
        }
        return max(dp0[n][m], dp1[n][m]);
    }
    
public:
    int maxSizeSlices(vector<int>& slices) {
        int n = slices.size();  // 3n
        int pick = n / 3;
        
        // Case 1: ไม่เลือก slices[0]
        vector<int> v1(slices.begin() + 1, slices.end());
        int ans1 = solve(v1, pick);
        
        // Case 2: เลือก slices[0] → ไม่เลือก slices[1] และ slices[n-1]
        vector<int> v2(slices.begin() + 2, slices.end() - 1);
        int ans2 = slices[0] + solve(v2, 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;
}

ความซับซ้อน

• Time: O(n²) = O((3n) × n) = O(n²)
• Space: O(n²) (สามารถลดเป็น O(n) ได้ด้วย Rolling Array)

Input / Output

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