C++ですべての本を購入するための最小コストを見つける

n個の要素の配列があるとします。これらはそれらの評価です。次の条件で、すべての本を購入するための最小コストを見つけます-

• 各本の費用は少なくとも1ドルになります
• 評価が隣接する本よりも高い場合、本は隣接する（左または右）よりもコストが高くなります。

したがって、たとえば、評価配列が[1、3、4、3、7、1]の場合、出力は10、As 1 + 2 + 3 + 1 + 2 + 1 =10

これを解決するには、LtoRとRtoLという2つの配列を作成し、それらを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