Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में जंप गेम V

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

  • i + x जहां: i + x < n और x की सीमा 1 से d है।

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

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

यदि इनपुट d = 2 और ऊंचाईयां हैं -

C++ में जंप गेम V

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

हल करने के चरण

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

  • solve() फ़ंक्शन परिभाषित करें जो सरणी arr, idx, d लेता है

  • यदि dp[idx] != -1 तो dp[idx] लौटाएं

  • ret := 1, n := arr का आकार

  • दाएं ओर (idx+1 से idx+d तक) जाएं: यदि arr[i] >= arr[idx] तो ब्रेक करें, अन्यथा ret = max(ret, 1 + solve(arr, i, d))

  • बाएं ओर (idx-1 से idx-d तक) जाएं: यदि arr[i] >= arr[idx] तो ब्रेक करें, अन्यथा ret = max(ret, 1 + solve(arr, i, d))

  • dp[idx] := ret, ret लौटाएं

  • मुख्य विधि से: सभी इंडेक्स के लिए solve कॉल करें और अधिकतम लौटाएं

उदाहरण

#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; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<int> v = {6,4,14,6,8,13,9,7,10,6,12}; 
    cout << (ob.maxJumps(v, 2)); 
    return 0; 
}

इनपुट

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

आउटपुट

4
  1. C++ में जंप गेम IV C++ में जंप गेम IV

    मान लीजिए हमारे पास arr नामक पूर्णांकों की एक सरणी है। हम प्रारंभ में इंडेक्स 0 पर हैं। एक चरण में हम इंडेक्स i से i + x पर कूद सकते हैं जहां: i + x = 0, j जहां: arr[i] और arr[j] समान हैं और i और j समान नहीं हैं। यहां n सरणी का आकार है। हमें सरणी के अंतिम इंडेक्स तक पहुंचने के लिए न्यूनतम चरणों की स

  1. - Python में जंप गेम II

    मान लीजिए हमारे पास पूर्णांकों की एक सरणी है, जहां सभी तत्व धनात्मक हैं। प्रारंभिक प्रारंभिक बिंदु इंडेक्स 1 पर है। सरणी में प्रत्येक तत्व उस स्थिति पर हमारी अधिकतम छलांग लंबाई दर्शाता है। हमारा लक्ष्य अंतिम कोशिका तक कम से कम छलांग के साथ पहुंचना है। इसलिए यदि सरणी [2,3,1,1,4] जैसी है, तो आउटपुट 2

  1. - पायथन में जंप गेम

    मान लीजिए हमारे पास गैर-ऋणात्मक पूर्णांकों की एक सरणी है; हम सरणी के पहले इंडेक्स पर प्रारंभिक रूप से स्थित हैं। दी गई सरणी में प्रत्येक तत्व उस स्थिति पर हमारी अधिकतम जंप लंबाई को दर्शाता है। हमें यह निर्धारित करना है कि क्या हम अंतिम इंडेक्स तक पहुंच सकते हैं या नहीं। इसलिए यदि सरणी [2,3,1,1,4] है