সব বই কেনার ন্যূনতম খরচ বের করা C++-তে

মনে করুন আমাদের n উপাদানের একটি অ্যারে আছে। এগুলো তাদের রেটিং। সব বই কেনার ন্যূনতম খরচ বের করতে হবে, নিচের শর্তে -

• প্রতিটি বইয়ের খরচ কমপক্ষে ১ ডলার
• একটি বইয়ের খরচ তার পাশের (বাম বা ডান) বইয়ের চেয়ে বেশি হবে যদি রেটিং বেশি হয়।

তাই উদাহরণস্বরূপ, যদি রেটিং অ্যারে হয় [1, 3, 4, 3, 7, 1], তবে আউটপুট হবে 10, কারণ 1 + 2 + 3 + 1 + 2 + 1 = 10

এটি সমাধানের জন্য, আমাদের দুটি অ্যারে বানাতে হবে LtoR, এবং RtoL, এবং সেগুলো ১ দিয়ে ফিল করুন, এখন নিচের ধাপগুলো অনুসরণ করুন -

• বাম থেকে ডানে ট্রাভার্স করুন, তারপর LtoR ফিল করুন, এবং দেওয়া অ্যারের পূর্ববর্তী রেটিং দেখে আপডেট করুন। আমরা দেওয়া অ্যারের পরবর্তী রেটিং এর চিন্তা করছি না
• ডান থেকে বাম ট্রাভার্স করুন, তারপর RtoL ফিল করুন, এবং দেওয়া অ্যারের পরবর্তী রেটিং দেখে আপডেট করুন। আমরা দেওয়া অ্যারের পূর্ববর্তী রেটিং এর চিন্তা করছি না
• দুই অ্যারে LtoR এবং RtoL-এ i-তম পজিশনের সর্বোচ্চ মান নিন, তারপর সেটি রেজাল্টে যোগ করুন।

উদাহরণ

#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