C++ में सरणी से तत्वों को हटाकर प्राप्त किए जा सकने वाले अधिकतम अंक खोजें

अवधारणा

एक दी गई सरणी A के संबंध में जिसमें N तत्व हैं और दो पूर्णांक l और r जहां, 1≤ a_x ≤ 10⁵ और 1≤ l≤ r≤ N। हम सरणी के किसी भी तत्व (मान लें a_x) का चयन कर सकते हैं और उसे हटा सकते हैं, और साथ ही a_x+1, a_x+2 … a_x+R और a_x-1, a_x-2 … a_x-L के बराबर सभी तत्वों को सरणी से हटा सकते हैं। यह चरण a_x अंक खर्च करेगा। हमारा कार्य सरणी से सभी तत्वों को हटाने के बाद कुल लागत को अधिकतम करना है।

इनपुट

2 1 2 3 2 2 1 l = 1, r = 1

आउटपुट

8

यहां, हम 2 को हटाने के लिए चुनते हैं, फिर दिए गए l और r रेंज के अनुसार (2-1)=1 और (2+1)=3 को हटाने की आवश्यकता होगी।

इसे तब तक दोहराएं जब तक 2 पूरी तरह से हट न जाए। तो, कुल लागत = 2*4 = 8।

इनपुट

2 4 2 10 5 l = 1, r = 2

आउटपुट

18

यहां, हम 2 को हटाने के लिए चुनते हैं, फिर 5 और फिर 10।

तो कुल लागत = 2*2 + 5 + 10 = 19।

विधि

अब, हम सभी तत्वों की गिनती निर्धारित करेंगे। मान लें एक तत्व X चुना जाता है तो, [X-l, X+r] रेंज में सभी तत्व हटा दिए जाएंगे। वर्तमान में, हम l और r से न्यूनतम रेंज चुनते हैं और निर्धारित करते हैं कि जब तत्व X चुना जाता है तो किन तत्वों को हटाया जाना है। परिणाम पहले से हटाए गए तत्वों और जब तत्व X हटाया जाता है, का अधिकतम होगा। अब, हम पहले से हटाए गए तत्वों के परिणाम को संग्रहीत करने के लिए डायनामिक प्रोग्रामिंग लागू करेंगे और इसे आगे लागू करेंगे।

उदाहरण

// C++ program to find maximum cost after // deleting all the elements form the array #include <bits/stdc++.h> using namespace std; // अधिकतम लागत प्राप्त करने वाला फ़ंक्शन int maxCost(int a[], int m, int L, int R){    int mx1 = 0, k1;    // सरणी के अधिकतम तत्व को निर्धारित करें।    for (int p = 0; p < m; ++p)       mx1 = max(mx1, a[p]);    // सभी तत्वों की गिनती को शून्य से इनिशियलाइज़ करने के लिए उपयोग किया जाता है।    int count1[mx1 + 1];    memset(count1, 0, sizeof(count1));    // सरणी के सभी तत्वों की आवृत्ति की गणना करें।    for (int p = 0; p < m; p++)       count1[a[p]]++;    // हटाए गए तत्वों की लागत संग्रहीत करने के लिए उपयोग किया जाता है।    int res1[mx1 + 1];    res1[0] = 0;    // L और R से न्यूनतम रेंज चुनना।    L = min(L, R);    for (int num1 = 1; num1 <= mx1; num1++) {       // निर्धारित करता है कि जब तत्व num चुना जाता है तो किन तत्वों को हटाया जाना है।       k1 = max(num1 - L - 1, 0);       // तत्व num का चयन करते समय या न करते समय अधिकतम प्राप्त करें।       res1[num1] = max(res1[num1 - 1], num1 * count1[num1] +       res1[k1]);    }    return res1[mx1]; } // ड्राइवर प्रोग्राम int main(){    int a1[] = { 1, 1, 3, 3, 3, 2, 4 }, l1 = 1, r1 = 1;    int a2[] = { 2, 4, 2, 10, 5 }, l2 = 1, r2 = 2;    // सरणी का आकार    int n1 = sizeof(a1) / sizeof(a1[0]);    int n2 = sizeof(a2) / sizeof(a2[0]);    // अधिकतम लागत खोजने के लिए फ़ंक्शन कॉल    cout<<"Maximum Cost for First Example:" << maxCost(a1, n1, l1,r1)<<endl;    cout<<"Maximum Cost for Second Example:" << maxCost(a2, n2, l2,r2);    return 0; }

आउटपुट

Maximum Cost for First Example:11 Maximum Cost for Second Example:19