Giả sử chúng ta có một mảng gồm n phần tử. Đây là xếp hạng của họ. Tìm chi phí tối thiểu để mua tất cả sách, với điều kiện sau -
- Giá của mỗi cuốn sách sẽ ít nhất là 1 đô la
- Sách có giá cao hơn sách liền kề (trái hoặc phải) nếu xếp hạng cao hơn sách liền kề.
Vì vậy, ví dụ:nếu mảng xếp hạng như [1, 3, 4, 3, 7, 1], thì đầu ra là 10, Như 1 + 2 + 3 + 1 + 2 + 1 =10
Để giải quyết vấn đề này, chúng ta phải tạo hai mảng có tên là LtoR và RtoL và điền chúng bằng 1, bây giờ hãy làm theo các bước sau -
- Di chuyển từ trái sang phải, sau đó điền LtoR và cập nhật nó bằng cách xem xếp hạng trước đó của mảng đã cho. Chúng tôi không quan tâm đến xếp hạng tiếp theo của mảng đã cho
- Di chuyển từ phải sang trái, sau đó điền RtoL và cập nhật nó bằng cách xem xếp hạng trước đó của mảng đã cho. Chúng tôi không quan tâm đến xếp hạng tiếp theo của mảng đã cho
- Để có giá trị lớn nhất của vị trí thứ i trong cả mảng LtoR và RtoL, hãy thêm nó vào kết quả.
Ví dụ
#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);
} Đầu ra
Minimum cost is: 15