หาต้นทุนน้อยที่สุดในการซื้อหนังสือทั้งหมดใน C++

สมมติว่ามีอาร์เรย์ n องค์ประกอบ นี่คือคะแนน (Ratings) ของพวกเขา หาต้นทุนน้อยที่สุดในการซื้อหนังสือทั้งหมด ภายใต้เงื่อนไขดังนี้:

• ต้นทุนของหนังสือแต่ละเล่มจะต้องมีอย่างน้อย 1 ดอลลาร์
• หนังสือที่มีคะแนนสูงกว่าจะมีต้นทุนมากกว่าหนังสือที่อยู่ติดกัน (ซ้ายหรือขวา)

ดังนั้นตัวอย่างเช่น ถ้าอาร์เรย์คะแนนเป็น [1, 3, 4, 3, 7, 1] ผลลัพธ์คือ 10 เพราะ 1 + 2 + 3 + 1 + 2 + 1 = 10

เพื่อแก้ปัญหานี้ เราต้องสร้างอาร์เรย์สองอาร์เรย์ชื่อ LtoR และ RtoL และเติมด้วย 1 ตอนนี้ทำตามขั้นตอนเหล่านี้:

• เดินทางจากซ้ายไปขวา แล้วเติม LtoR และอัปเดตโดยดูคะแนนก่อนหน้าของอาร์เรย์ที่กำหนด เราไม่สนใจคะแนนถัดไปของอาร์เรย์ที่กำหนด
• เดินทางจากขวาไปซ้าย แล้วเติม RtoL และอัปเดตโดยดูคะแนนก่อนหน้าของอาร์เรย์ที่กำหนด เราไม่สนใจคะแนนถัดไปของอาร์เรย์ที่กำหนด
• สำหรับค่าสูงสุดของตำแหน่งที่ i ในทั้งสองอาร์เรย์ LtoR และ RtoL ให้บวกเข้าไปในผลลัพธ์

ตัวอย่าง

#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