C++ में 3n स्लाइस के साथ पिज़्ज़ा

मान लीजिए कि एक पिज्जा है जिसमें अलग-अलग आकार के 3n स्लाइस हैं, मैं और मेरे दो दोस्त पिज्जा के स्लाइस इस प्रकार लेंगे -

मैं कोई भी पिज़्ज़ा स्लाइस चुनूंगा।
मेरा दोस्त अमल मेरी पसंद की घड़ी की विपरीत दिशा में अगला टुकड़ा उठाएगा।
मेरा दोस्त बिमल मेरी पसंद की अगली स्लाइस को दक्षिणावर्त दिशा में उठाएगा।
इन चरणों को तब तक दोहराएं जब तक कि पिज़्ज़ा के और टुकड़े न रह जाएँ।

पिज्जा स्लाइस के आकार को दक्षिणावर्त दिशा में गोलाकार सरणी स्लाइस द्वारा दर्शाया जाता है। हमें स्लाइस आकारों का अधिकतम संभव योग खोजना होगा जो मेरे पास हो सकता है।

तो, अगर इनपुट [9,8,6,1,1,8],

. जैसा है

C++ में 3n स्लाइस के साथ पिज़्ज़ा

तो आउटपुट 16 होगा, जैसा कि प्रत्येक मोड़ में आकार 8 का पिज़्ज़ा स्लाइस चुनें। अगर मैं आकार 9 के साथ स्लाइस चुनता हूं तो मेरे दोस्त आकार 8 के स्लाइस चुनेंगे।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

एक फ़ंक्शन हल करें () को परिभाषित करें, यह एक सरणी v, और एक तर्क m लेगा,

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

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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;
   }
};
main(){
   Solution ob;
   vector<int> v = {9,8,6,1,1,8};
   cout << (ob.maxSizeSlices(v));
}

इनपुट

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