ধরুন আমাদের n উপাদানের একটি অ্যারে আছে। এগুলো তাদের রেটিং। সমস্ত বই কেনার ন্যূনতম খরচ খুঁজুন, নিম্নলিখিত শর্ত সহ -
- প্রতিটি বইয়ের দাম হবে কমপক্ষে ১ ডলার
- একটি বইয়ের মূল্য সংলগ্ন (বাম বা ডান) থেকে বেশি হয় যদি রেটিং সন্নিহিত থেকে বেশি হয়।
সুতরাং উদাহরণস্বরূপ, যদি রেটিং অ্যারে হয় [1, 3, 4, 3, 7, 1], তাহলে আউটপুট 10, যেমন 1 + 2 + 3 + 1 + 2 + 1 =10
এটি সমাধান করার জন্য, আমাদের LtoR এবং RtoL নামে দুটি অ্যারে তৈরি করতে হবে এবং সেগুলিকে 1 দিয়ে পূরণ করতে হবে, এখন এই পদক্ষেপগুলি অনুসরণ করুন -
- বাম থেকে ডানে যান, তারপর LtoR পূরণ করুন এবং প্রদত্ত অ্যারের পূর্ববর্তী রেটিং দেখে এটি আপডেট করুন। আমরা প্রদত্ত অ্যারের পরবর্তী রেটিং নিয়ে চিন্তা করছি না
- ডান থেকে বাম দিকে যান, তারপর RtoL পূরণ করুন এবং প্রদত্ত অ্যারের পূর্ববর্তী রেটিং দেখে আপডেট করুন। আমরা প্রদত্ত অ্যারের পরবর্তী রেটিং নিয়ে চিন্তা করছি না
- LtoR এবং RtoL উভয় অ্যারেতে ith অবস্থানের সর্বোচ্চ মানের জন্য, তারপর ফলাফলে এটি যোগ করুন।
উদাহরণ
#include<iostream>
using namespace std;
int getMinCost(int ratings[], int n) {
int res = 0;
int LtoR[n];
int RtoL[n];
for(int i = 0; i<n; i++){
LtoR[i] = RtoL[i] = 1;
}
for (int i = 1; i < n; i++)
if (ratings[i] > ratings[i - 1])
LtoR[i] = LtoR[i - 1] + 1;
for (int i = n - 2; i >= 0; i--)
if (ratings[i] > ratings[i + 1])
RtoL[i] = RtoL[i + 1] + 1;
for (int i = 0; i < n; i++)
res += max(LtoR[i], RtoL[i]);
return res;
}
int main() {
int ratings[] = { 1, 6, 8, 3, 4, 1, 5, 7 };
int n = sizeof(ratings) / sizeof(ratings[0]);
cout << "Minimum cost is: " << getMinCost(ratings, n);
} আউটপুট
Minimum cost is: 15
