ধারণা
একটি প্রদত্ত অ্যারের সাপেক্ষে A যার N উপাদান রয়েছে এবং দুটি পূর্ণসংখ্যা l এবং r যেখানে, 1≤ ax ≤ 10 5 এবং 1≤ l≤ r≤ N. আমরা অ্যারের যেকোন উপাদান নির্বাচন করতে পারি (আসুন ax বলি) এবং মুছে ফেলতে পারি, এবং একটিx এর সমান সমস্ত উপাদান মুছে ফেলতে পারি। +1, ax +2 … ax +R এবং ax -1, ax -2 … ax -এল অ্যারে থেকে। এই ধাপে কুঠার পয়েন্ট খরচ হবে. আমাদের কাজ হল অ্যারে থেকে সমস্ত উপাদান মুছে ফেলার পরে মোট খরচ সর্বাধিক করা।
ইনপুট
2 1 2 3 2 2 1 l = 1, r = 1
আউটপুট
8
এখানে, আমরা মুছে ফেলার জন্য 2 বেছে নিই, তারপর (2-1)=1 এবং (2+1)=3 যথাক্রমে l এবং r পরিসরের জন্য মুছে ফেলতে হবে।
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] মুছে ফেলা হবে। বর্তমানে, আমরা ল্যান্ড r থেকে ন্যূনতম পরিসর বেছে নিই এবং X এলিমেন্ট বাছাই করা হলে কোন উপাদানগুলিকে মুছে ফেলতে হবে তা নির্ধারণ করি। ফলাফলগুলি পূর্বে মুছে ফেলা উপাদানগুলির সর্বাধিক হবে এবং যখন উপাদান X মুছে ফেলা হবে। এখন, আমরা পূর্বে মুছে ফেলা উপাদানগুলির ফলাফল সংরক্ষণ করতে এবং আরও কার্যকর করার জন্য গতিশীল প্রোগ্রামিং প্রয়োগ করব৷
উদাহরণ
// C++ program to find maximum cost after
// deleting all the elements form the array
#include <bits/stdc++.h>
using namespace std;
// Shows function to return maximum cost obtained
int maxCost(int a[], int m, int L, int R){
int mx1 = 0, k1;
// Determine maximum element of the array.
for (int p = 0; p < m; ++p)
mx1 = max(mx1, a[p]);
// Used to initialize count of all elements to zero.
int count1[mx1 + 1];
memset(count1, 0, sizeof(count1));
// Compute frequency of all elements of array.
for (int p = 0; p < m; p++)
count1[a[p]]++;
// Used to store cost of deleted elements.
int res1[mx1 + 1];
res1[0] = 0;
// Choosing minimum range from L and R.
L = min(L, R);
for (int num1 = 1; num1 <= mx1; num1++) {
// Determines upto which elements are to be
// deleted when element num is selected.
k1 = max(num1 - L - 1, 0);
// Obtain maximum when selecting element num or not.
res1[num1] = max(res1[num1 - 1], num1 * count1[num1] +
res1[k1]);
}
return res1[mx1];
}
// Driver program
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;
// size of array
int n1 = sizeof(a1) / sizeof(a1[0]);
int n2 = sizeof(a2) / sizeof(a2[0]);
// function call to find maximum cost
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
