Tối thiểu hóa số gấu bông phân phát cho học sinh C++

Đề bài

Cho n học sinh với điểm số. Phân phát gấu bông thỏa mãn: 1. Mọi học sinh ≥ 1 gấu 2. Học sinh ngồi cạnh, điểm cao hơn → gấu nhiều hơn 3. Điểm bằng nhau → có thể số gấu khác nhau
Tối thiểu hóa tổng số gấu.

Giải thuật (Dynamic Programming)

1. Khởi tạo mảng table[n] = 1 (mỗi học sinh 1 gấu)
2. Duyệt trái→phải: nếu điểm[i+1] > điểm[i] thì table[i+1] = table[i] + 1
3. Duyệt phải→trái: nếu điểm[i] > điểm[i+1] và table[i] ≤ table[i+1] thì table[i] = table[i+1] + 1
4. Tổng = sum(table)

Ví dụ minh họa

#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

int teddieDistribution(int *marks, int n) {
    int table[n];
    fill(table, table + n, 1);
    
    // Trai -> Phai
    for (int i = 0; i < n - 1; ++i)
        if (marks[i + 1] > marks[i])
            table[i + 1] = table[i] + 1;
    
    // Phai -> Trai
    for (int i = n - 2; i >= 0; --i)
        if (marks[i] > marks[i + 1] && table[i] <= table[i + 1])
            table[i] = table[i + 1] + 1;
    
    int total = 0;
    for (int i = 0; i < n; ++i) total += table[i];
    return total;
}

int main() {
    int marks[] = {2, 6, 5, 2, 3, 7};
    cout << "Tong gau bong: " << teddieDistribution(marks, SIZE(marks)) << "\n";
    return 0;
}

Kết quả

Tong gau bong: 12