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

C++ में दिए गए स्ट्रिंग से k अद्वितीय सबसीक्वेंसेस ढूंढने की लागत निकालने का प्रोग्राम


परिचय

मान लीजिए, हमारे पास एक स्ट्रिंग s और एक अन्य मान k है। हमें s के कुछ सबसीक्वेंसेस (subsequences) चुनने हैं, ताकि हमें k अद्वितीय सबसीक्वेंसेस मिल सकें। यहां, एक सबसीक्वेंस चुनने की लागत length(s) - length(subsequence) के बराबर होती है। तो, हमें k अद्वितीय सबसीक्वेंसेस चुनने के बाद न्यूनतम कुल लागत ढूंढनी है। यदि हम इस सेट को ढूंढने में असमर्थ हैं, तो हम -1 वापस करेंगे। हम खाली स्ट्रिंग को एक वैध सबसीक्वेंस मानेंगे।

तो, यदि इनपुट s = "pqrs", k = 4 है, तो आउटपुट 3 होगा।

समाधान दृष्टिकोण

डायनामिक प्रोग्रामिंग का उपयोग करके dp[i][j] = s के पहले i कैरेक्टर्स का उपयोग करके लंबाई j के अद्वितीय सबसीक्वेंसेस की संख्या। फिर लालची तरीके से सबसे लंबे सबसीक्वेंसेस पहले चुनें (कम लागत)।

उदाहरण कोड

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

int solve(string s, int k) {
    int n = s.size();
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    unordered_map<char, int> last;
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        dp[i + 1][0] = 1;
        for (int j = (i + 1); j >= 1; j--) {
            dp[i + 1][j] = dp[i][j] + dp[i][j - 1];
        }
        if (last.find(s[i]) != last.end()) {
            for (int j = 0; j <= last[s[i]]; j++) {
                dp[i + 1][j + 1] -= dp[last[s[i]]][j];
            }
        }
        last[s[i]] = i;
    }
    int cost = 0;
    for (int i = n; i >= 0; i--) {
        int val = min(k, dp[n][i]);
        cost += (val * (n - i));
        k -= dp[n][i];
        if (k <= 0) break;
    }
    if (k <= 0) return cost;
    return -1;
}

int main(){
    cout << solve("pqrs", 4) << endl;
    return 0;
}

इनपुट

"pqrs", 4

आउटपुट

3

व्याख्या

"pqrs" के अद्वितीय सबसीक्वेंसेस: लंबाई 4: "pqrs" (1), लंबाई 3: "pqr", "pqs", "prs", "qrs" (4), लंबाई 2: 6, लंबाई 1: 4, लंबाई 0: 1।

k=4 के लिए: सबसे लंबे चुनें: "pqrs" (लागत 0), फिर लंबाई 3 से 3 सबसीक्वेंसेस (लागत 1 प्रत्येक) = कुल लागत 3।

निष्कर्ष

DP टेबल सभी लंबाई के अद्वितीय सबसीक्वेंसेस गिनता है, डुप्लिकेट कैरेक्टर्स को हैंडल करते हुए। लालची चयन न्यूनतम लागत सुनिश्चित करता है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।


  1. - दिए गए ग्राफ में q क्वेरी के लिए सबसे छोटे लागत पथ को ढूंढने के लिए C++ प्रोग्राम

    मान लीजिए, हमें एक ग्राफ दिया गया है जिसमें n शीर्ष हैं और यह न्यूनतम रूप से जुड़ा हुआ है। किनारे हमें एक ऐरे में दिए गए हैं जहां किनारे {स्रोत, गंतव्य, वजन} प्रारूप में दिए गए हैं। अब, हमें q संख्या के क्वेरी दिए गए हैं जहां प्रत्येक क्वेरी {स्रोत, गंतव्य} प्रारूप में है। हमें शीर्ष k के माध्यम से

  1. - दिए गए पूर्णांकों से अधिकतम संभावित टैली ज्ञात करने का C++ प्रोग्राम

    मान लीजिए हमें दो पूर्णांक n और m दिए गए हैं और k टपल्स हैं जिनमें चार पूर्णांक {ai, bi, ci, di} हैं। चार सरणियाँ a, b, c, d दी गई हैं जहाँ a[i] i-वें टपल का a मान दर्शाता है। अब एक अनुक्रम dp पर विचार करें जिसमें n धनात्मक पूर्णांक हों और 1 ≤ dp[1] < dp[2] < ... < dp[n] ≤ m। हम एक मेट्रिक टैली परि

  1. दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए n वर्टेक्स और m एज वाला एक अनभारित, निदेश रहित ग्राफ दिया गया है। ग्राफ में एक ब्रिज एज वह एज है जिसे हटाने से ग्राफ असंबद्ध हो जाता है। हमें दिए गए ग्राफ में ऐसी एज की संख्या ज्ञात करनी है। ग्राफ में समानांतर एज या सेल्फ-लूप नहीं हैं। उदाहरण के लिए, यदि इनपुट है n = 5, m = 6, edges = {{1