C++ में लंबाई a, b और c के अधिकतम लाइन सेगमेंट की संख्या

दिया गया कार्य दिए गए धनात्मक पूर्णांक N से लंबाई a, b और c के अधिकतम लाइन सेगमेंट की संख्या ढूंढना है जो बनाए जा सकते हैं।

उदाहरण से समझते हैं

इनपुट - N=8, a=3, b=1, c=2

आउटपुट - 8

व्याख्या - N को b के 8 सेगमेंट में विभाजित किया जा सकता है जो बनाए जा सकने वाले सेगमेंट की अधिकतम संख्या है।

इनपुट - N=13, a=2, b=7, c=3

आउटपुट - 6

प्रयुक्त दृष्टिकोण

MaxSegment() फंक्शन में MaxSeg[N + 1] टाइप का एक ऐरे घोषित करें और इसे -1 मान से आरंभ करें।
शून्यवें इंडेक्स को 0 के बराबर रखें क्योंकि इसमें कोई सेगमेंट नहीं होगा।
i=0 से i<N तक लूप चलाएं और चेक करें यदि (MaxSeg[i] != -1)।
उपरोक्त if स्टेटमेंट के अंदर एक और स्टेटमेंट डालें if(i + a <= N) और MaxSeg[i + a] = max(MaxSeg[i] + 1, MaxSeg[i + a]) रखें।
b और c दोनों के लिए उपरोक्त चरण दोहराएं।
लूप के बाहर, MaxSeg[N] वापस करें।

C++ प्रोग्राम उदाहरण

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

int MaxSegment(int N, int a, int b, int c) {
    /* यह स्टोर करेगा कि प्रत्येक इंडेक्स में अधिकतम कितने सेगमेंट हो सकते हैं */
    int MaxSeg[N + 1];
    
    // आरंभीकरण
    memset(MaxSeg, -1, sizeof(MaxSeg));
    
    // 0वां इंडेक्स में 0 सेगमेंट होंगे
    MaxSeg[0] = 0;
    
    // n तक हर सेगमेंट के लिए ट्रैवर्स करना
    for (int i = 0; i < N; i++) {
        if (MaxSeg[i] != -1) {
            if (i + a <= N) {
                MaxSeg[i + a] = max(MaxSeg[i] + 1, MaxSeg[i + a]);
            }
            if (i + b <= N) {
                MaxSeg[i + b] = max(MaxSeg[i] + 1, MaxSeg[i + b]);
            }
            if (i + c <= N) {
                MaxSeg[i + c] = max(MaxSeg[i] + 1, MaxSeg[i + c]);
            }
        }
    }
    return MaxSeg[N];
}

int main() {
    int N = 13, a = 2, b = 7, c = 3;
    cout << MaxSegment(N, a, b, c);
    return 0;
}