C++-এ অ্যারে থেকে উপাদান মুছে সর্বোচ্চ পয়েন্ট লাভ করা

কনসেপ্ট

একটি অ্যারে A দেওয়া আছে যার Nটি উপাদান এবং দুটি পূর্ণসংখ্যা l ও r (১ ≤ aₓ ≤ ১০⁵, ১ ≤ l ≤ r ≤ N)। আমরা অ্যারে থেকে যেকোনো উপাদান (যেমন aₓ) বেছে নিতে পারি এবং তা মুছে ফেলতে পারি, সাথে সাথে aₓ+1, aₓ+2 ... aₓ+R এবং aₓ-1, aₓ-2 ... aₓ-L সমান সকল উপাদানও মুছে ফেলতে হবে। এই ধাপটি aₓ পয়েন্ট খরচ করবে। লক্ষ্য হল অ্যারের সব উপাদান মুছে ফেলার পর সর্বোচ্চ মোট খরচ (পয়েন্ট) অর্জন করা।

ইনপুট ১

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

আউটপুট ১

এখানে ২ বেছে নিয়ে মুছে ফেলা হয়েছে, ফলে (২-১)=১ এবং (২+১)=৩ মুছে ফেলতে হয়। এটি ২ সম্পূর্ণ মুছে যাওয়ার পর্যন্ত চালিয়ে যেতে হবে। মোট খরচ = ২×৪ = ৮।

ইনপুট ২

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

আউটপুট ২

এখানে ২, তারপর ৫, তারপর ১০ বেছে নিয়ে মুছে ফেলা হয়েছে। মোট খরচ = ২×২ + ৫ + ১০ = ১৯। (নোট: আউটপুটে ১৮ লেখা আছে কিন্তু ব্যাখ্যায় ১৯।)

পদ্ধতি

প্রথমে সব উপাদানের ফ্রিকোয়েন্সি (ঘনত্ব) গণনা করুন। যদি উপাদান X বেছে নেওয়া হয়, তবে [X-l, X+r] রেঞ্জের সব উপাদান মুছে যাবে। l এবং r-র মধ্যে ন্যূনতম রেঞ্জ বেছে নিয়ে নির্ণয় করুন যে X বেছে নিলে কোন উপাদানগুলো মুছে যাবে। ডাইনামিক প্রোগ্রামিং ব্যবহার করে পূর্বে মুছে ফেলা উপাদানগুলোর ফলাফল সংরক্ষণ করুন এবং তা ব্যবহার করে আরও সমাধান করুন।

উদাহরণ (C++ কোড)

// C++ প্রোগ্রাম: অ্যারে থেকে সব উপাদান মুছে ফেলার পর সর্বোচ্চ খরচ নির্ণয়
#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 << "প্রথম উদাহরণের সর্বোচ্চ খরচ: " << maxCost(a1, n1, l1, r1) << endl;
    cout << "দ্বিতীয় উদাহরণের সর্বোচ্চ খরচ: " << maxCost(a2, n2, l2, r2);
    return 0;
}

আউটপুট

প্রথম উদাহরণের সর্বোচ্চ খরচ: 11
দ্বিতীয় উদাহরণের সর্বোচ্চ খরচ: 19