मान लीजिए हमारे पास n तत्वों का एक ऐरे है। ये उनकी रेटिंग हैं। निम्नलिखित शर्त के साथ सभी किताबें खरीदने के लिए न्यूनतम लागत खोजें -
- प्रत्येक किताब की लागत कम से कम 1 डॉलर होगी
- एक किताब की लागत आसन्न (बाएं या दाएं) से अधिक होगी यदि रेटिंग आसन्न से अधिक है।
तो उदाहरण के लिए, यदि रेटिंग ऐरे [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
