n개의 요소로 구성된 배열이 있다고 가정합니다. 이들의 평점입니다. 다음 조건에서 모든 책을 구입하는 데 필요한 최소 비용을 찾으십시오. -
- 각 책의 가격은 최소 1달러입니다.
- 평가가 인접 도서보다 높으면 도서의 비용이 인접 도서(왼쪽 또는 오른쪽)보다 높습니다.
예를 들어, 등급 배열이 [1, 3, 4, 3, 7, 1]과 같으면 출력은 10, As 1 + 2 + 3 + 1 + 2 + 1 =10
이 문제를 해결하려면 LtoR 및 RtoL이라는 두 개의 배열을 만들고 1로 채워야 합니다. 이제 다음 단계를 따르세요. -
- 왼쪽에서 오른쪽으로 이동한 다음 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