C++ में 3n स्लाइस वाली पिज्जा

समस्या विवरण

मान लीजिए 3n स्लाइस वाली एक पिज्जा है जिसके स्लाइस विभिन्न आकार के हैं। मैं और मेरे दो दोस्त पिज्जा के स्लाइस निम्नानुसार लेंगे:

मैं कोई भी पिज्जा स्लाइस चुनूंगा।
मेरा दोस्त अमल मेरे चुने हुए स्लाइस के एंटी-क्लॉकवाइज दिशा में अगला स्लाइस लेगा।
मेरा दोस्त बिमल मेरे चुने हुए स्लाइस के क्लॉकवाइज दिशा में अगला स्लाइस लेगा।
इन चरणों को तब तक दोहराएं जब तक पिज्जा के स्लाइस नहीं बचते।

पिज्जा स्लाइस के आकार को क्लॉकवाइज दिशा में सर्कुलर सरणी slices द्वारा दर्शाया जाता है। हमें उन स्लाइस आकारों के अधिकतम संभावित योग को ढूंढना है जो मुझे मिल सकते हैं।

उदाहरण

यदि इनपुट है: [9,8,6,1,1,8], तो आउटपुट होगा 16, क्योंकि प्रत्येक बारी में आकार 8 का पिज्जा स्लाइस चुनें। यदि मैं आकार 9 का स्लाइस चुनता हूं तो मेरे दोस्त आकार 8 के स्लाइस चुनेंगे।

C++ में 3n स्लाइस वाली पिज्जा

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें (डायनामिक प्रोग्रामिंग):

solve() नामक एक फ़ंक्शन परिभाषित करें, जो एक सरणी v और एक तर्क m लेता है:
- n := v का आकार
- आकार (n + 1) x (m + 1) के दो 2D सरणी dp1 और dp2 परिभाषित करें
- i := 0 से आरंभ करें, जब i < n, i को 1 से बढ़ाते हुए:
  - j := 0 से आरंभ करें, जब j <= m, j को 1 से बढ़ाते हुए:
    - x := v[i]
    - यदि j < m:
      - dp2[i + 1][j + 1] = dp2[i + 1][j + 1] और dp1[i][j] + x का अधिकतम
      - dp1[i + 1][j] = dp1[i + 1][j], dp2[i][j] और dp1[i][j] का अधिकतम
- dp1[n][m] और dp2[n][m] का अधिकतम लौटाएं
मुख्य विधि से:
- n := slices का आकार
- ret := 0
- ret := solve(slices इंडेक्स 1 से अंत तक, n/3) और slices[0] + solve(slices इंडेक्स 2 से अंत-1 तक, n/3 - 1) का अधिकतम
- ret लौटाएं

C++ कार्यान्वयन

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

class Solution {
public:
    int solve(vector<int> v, int m) {
        int n = v.size();
        vector<vector<int>> dp1(n + 1, vector<int>(m + 1));
        vector<vector<int>> dp2(n + 1, vector<int>(m + 1));
        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]);
    }
    int maxSizeSlices(vector<int>& slices) {
        int n = slices.size();
        int ret = 0;
        ret = max(solve(vector<int>(slices.begin() + 1, slices.end()), n / 3),
                  slices[0] + solve(vector<int>(slices.begin() + 2, slices.end() - 1), n / 3 - 1));
        return ret;
    }
};

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

इनपुट

{9,8,6,1,1,8}