Cho mảng đánh giá sách. Chi phí mỗi sách ≥ 1. Sách có đánh giá cao hơn sách bên cạnh phải có chi phí cao hơn. Tìm tổng chi phí nhỏ nhất. Ví dụ [1,3,4,3,7,1] → 10 (1+2+3+1+2+1).
Dùng hai mảng LtoR và RtoL khởi tạo 1. Duyệt trái sang phải cập nhật LtoR nếu đánh giá tăng. Duyệt phải sang trái cập nhật RtoL. Chi phí mỗi sách = max(LtoR[i], RtoL[i]).
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); }
Kết quả
Minimum cost is: 15