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

सबसे ऊंचा बिलबोर्ड C++ में

मान लीजिए हम एक बिलबोर्ड स्थापित कर रहे हैं और हम चाहते हैं कि इसकी ऊंचाई सबसे अधिक हो। बिलबोर्ड के दोनों तरफ दो स्टील सपोर्ट होंगे। प्रत्येक सपोर्ट की ऊंचाई समान होनी चाहिए। हमारे पास रॉड्स का एक संग्रह है जिन्हें एक साथ वेल्ड किया जा सकता है। हमें अपने बिलबोर्ड इंस्टॉलेशन की सबसे बड़ी संभव ऊंचाई ढूंढनी है। यदि हम बिलबोर्ड को सपोर्ट नहीं कर सकते, तो 0 वापस करें।

उदाहरण के लिए, यदि इनपुट [1,2,2,3,3,3,4] है, तो आउटपुट 9 होगा, क्योंकि हमारे पास [1,2,2,4] और [3,3,3] जैसे सबसेट हैं।

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

हम दो सपोर्ट के बीच अंतर को ट्रैक करने के लिए डायनामिक प्रोग्रामिंग का उपयोग करते हैं:

  • dp[i][j] = पहले i रॉड्स का उपयोग करके अंतर j-5000 के साथ अधिकतम ऊंचाई

  • ऑफसेट 5000 नकारात्मक अंतर को संभालता है

  • प्रत्येक रॉड के लिए, तीन विकल्पों पर विचार करें: सपोर्ट 1 में जोड़ें, सपोर्ट 2 में जोड़ें, या छोड़ दें

  • dp टेबल को तदनुसार अपडेट करें

  • अंतिम उत्तर dp[n][5000] है (अंतर 0)

उदाहरण

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

class Solution { 
public: 
    int tallestBillboard(vector<int>& rods){ 
        int sum = 0; 
        int n = rods.size(); 
        int N = 2 * 5000; 
        
        vector<vector<int> > dp(n + 1, vector<int>(N + 1, -1)); 
        dp[0][5000] = 0; 
        
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j <= N; j++) { 
                int x = rods[i]; 
                if (j - x >= 0 && dp[i][j - x] != -1) { 
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - x] + x); 
                } 
                if (j + x <= N && dp[i][j + x] != -1) { 
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j + x]); 
                } 
                if (dp[i][j] != -1) { 
                    dp[i + 1][j] = max(dp[i][j], dp[i + 1][j]); 
                } 
            } 
        } 
        return dp[n][5000]; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {1,2,2,3,3,3,4}; 
    cout << (ob.tallestBillboard(v)); 
    return 0;
}

इनपुट

{1,2,2,3,3,3,4}

आउटपुट

9
  1. - C++ में Switch स्टेटमेंट: एक पूर्ण गाइड

    C++ में Switch स्टेटमेंट का उपयोग कैसे करें कंडीशनल स्टेटमेंट्स सभी प्रोग्रामिंग भाषाओं की एक सामान्य विशेषता हैं। इन स्टेटमेंट्स का उपयोग प्रोग्राम के प्रवाह को नियंत्रित करने और यह निर्दिष्ट करने के लिए किया जाता है कि कोड के विशिष्ट ब्लॉक्स कब निष्पादित होने चाहिए। C++ में उपयोग किए जाने वाले मुख

  1. - C++ में मितव्ययी संख्या (Frugal Number)

    इस समस्या में, हमें एक धनात्मक पूर्णांक N दिया गया है। हमारा कार्य यह जांचने के लिए एक प्रोग्राम बनाना है कि दी गई संख्या मितव्ययी संख्या है या नहीं। मितव्ययी संख्या (FRUGAL NUMBER) − एक संख्या जिसके अंकों की संख्या उस संख्या के अभाज्य गुणनखंडन में अंकों की संख्या से सख्ती से अधिक है। उदाहरण &

  1. C++ में पेंटाटोप संख्या C++ में पेंटाटोप संख्या

    एक पेंटाटोप संख्या को पास्कल के त्रिभुज में पांचवीं संख्या के रूप में वर्णित किया गया है। अब, चूंकि यह पांचवीं संख्या है, इसका मतलब है कि पास्कल के त्रिभुज में कम से कम पांच संख्याएं होनी चाहिए, इसलिए इस श्रृंखला की पहली संख्या 1 4 6 4 1 से शुरू होती है जो पास्कल के त्रिभुज की चौथी पंक्ति है। तो, इस