सी++ में जंप गेम वी

मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी है जिसे arr और एक पूर्णांक d कहा जाता है। एक चरण में हम इंडेक्स i से −

• i + x जहां:i + x

• i - x जहां:i - x>=0 और x 1 से d की श्रेणी में।

यहाँ n सरणी का आकार है। इसके अलावा, हम केवल इंडेक्स i से इंडेक्स j पर कूद सकते हैं जब arr[i]> arr[j] और arr[i]> arr[k] i और j के बीच सभी इंडेक्स k के लिए। हम सरणी के किसी भी सूचकांक को चुन सकते हैं और कूदना शुरू कर सकते हैं। हमें अधिकतम संख्या में सूचकांकों का पता लगाना है जिन पर हम जा सकते हैं।

इसलिए, यदि इनपुट d =2 जैसा है और ऊंचाई समान है

तो आउटपुट 4 होगा, हम इंडेक्स 10 से शुरू कर सकते हैं। हम इंडेक्स 10 से कूद सकते हैं -> 8 -> 6 -> 7 जैसा कि दिखाया गया है। इसलिए यदि हम इंडेक्स 6 से शुरू करते हैं तो हम केवल इंडेक्स 7 पर जा सकते हैं। हम इंडेक्स 5 पर नहीं जा सकते क्योंकि 13> 9। हम इंडेक्स 4 पर नहीं जा सकते क्योंकि इंडेक्स 5 इंडेक्स 4 और 6 और 13> 9 के बीच है। और साथ ही, हम अनुक्रमणिका 3 से अनुक्रमणिका 2 या अनुक्रमणिका 1 पर नहीं जा सकता।

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

• एक सरणी dp परिभाषित करें

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

  लेगा

• अगर dp[idx] -1 के बराबर नहीं है, तो -

  • वापसी डीपी [आईडीएक्स]

• रिट :=1

• n :=गिरफ्तारी का आकार

• इनिशियलाइज़ i :=idx + 1 के लिए, जब i

  • अगर मैं> idx + d, तो −

    • लूप से बाहर आएं

  • अगर arr[i]>=arr[idx], तो −

    • लूप से बाहर आएं

  • ret :=अधिकतम रिट और 1 + हल करें(arr, i, d)

• इनिशियलाइज़ करने के लिए i :=idx-1, जब i>=0, अपडेट करें (i से 1 घटाएं), −

  करें

  • अगर मैं

    • लूप से बाहर आएं

  • अगर arr[i]>=arr[idx], तो −

    • लूप से बाहर आएं

  • ret :=अधिकतम रिट और 1 + हल करें(arr, i, d)

• डीपी [आईडीएक्स]:=सेवानिवृत्त

• वापसी रिट

• मुख्य विधि से निम्न कार्य करें -

• n :=गिरफ्तारी का आकार

• dp :=आकार n की एक सरणी को परिभाषित करें और इसे -1 से भरें

• रिट :=1

• इनिशियलाइज़ i :=0 के लिए, जब i

  • रिट :=अधिकतम रिट और सॉल्व (गिरफ्तारी, आई, डी)

• वापसी रिट

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector<int> dp;
   int solve(vector <int>& arr, int idx, int d){
      if (dp[idx] != -1)
      return dp[idx];
      int ret = 1;
      int n = arr.size();
      for (int i = idx + 1; i < n; i++) {
         if (i > idx + d)
         break;
         if (arr[i] >= arr[idx])
         break;
         ret = max(ret, 1 + solve(arr, i, d));
      }
      for (int i = idx - 1; i >= 0; i--) {
         if (i < idx - d)
         break;
         if (arr[i] >= arr[idx])
         break;
         ret = max(ret, 1 + solve(arr, i, d));
      }
      return dp[idx] = ret;
   }
   int maxJumps(vector<int>& arr, int d) {
      int n = arr.size();
      dp = vector<int>(n, -1);
      int ret = 1;
      for (int i = 0; i < n; i++) {
         ret = max(ret, solve(arr, i, d));
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {6,4,14,6,8,13,9,7,10,6,12};
   cout << (ob.maxJumps(v, 2));
}

इनपुट

{6,4,14,6,8,13,9,7,10,6,12}, 2

आउटपुट

4