Editorial for Chia buổi tập

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Gợi ý 1 - Chi phí của một buổi chỉ phụ thuộc vào đoạn nó nhận

Nếu buổi cuối cùng tập các tiết mục từ j+1 đến i, chi phí của buổi đó là giá trị lớn nhất trừ giá trị nhỏ nhất trong đoạn này.

Gợi ý 2 - Quy hoạch động theo số buổi và số tiết mục đã xếp

Đặt dp[g][i] là chi phí nhỏ nhất để chia i tiết mục đầu thành đúng g buổi. Thử mọi vị trí j làm điểm kết thúc của g-1 buổi đầu.

Lời giải đầy đủ

Công thức quy hoạch động

Đặt dp[g][i] là tổng chi phí nhỏ nhất khi chia i tiết mục đầu thành đúng g buổi liên tiếp, không rỗng.

Nếu buổi cuối bắt đầu sau tiết mục j, thì:

dp[g][i] = min(dp[g-1][j] + max(a[j+1..i]) - min(a[j+1..i])),

với g-1 <= j < i. Ta duyệt j lùi từ i-1 về g-1; trong lúc duyệt, cập nhật nhanh giá trị nhỏ nhất và lớn nhất của đoạn cuối.

Khởi tạo dp[0][0]=0; các trạng thái còn lại ban đầu là vô cực. Có thể chỉ giữ hàng g-1 và hàng g hiện tại.

Độ phức tạp

Thời gian: O(KN^2). Với N <= 500 và K <= 30, số chuyển trạng thái đủ nhỏ.
Bộ nhớ: O(N).

Code C++17

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    const long long INF = (1LL << 62);
    vector<long long> previous(n + 1, INF), current(n + 1, INF);
    previous[0] = 0;

    for (int groups = 1; groups <= k; ++groups) {
        fill(current.begin(), current.end(), INF);

        for (int i = groups; i <= n; ++i) {
            long long minimum = LLONG_MAX;
            long long maximum = LLONG_MIN;

            for (int j = i - 1; j >= groups - 1; --j) {
                minimum = min(minimum, a[j + 1]);
                maximum = max(maximum, a[j + 1]);
                if (previous[j] != INF) {
                    current[i] = min(current[i],
                                     previous[j] + maximum - minimum);
                }
            }
        }

        previous.swap(current);
    }

    cout << previous[n] << '\n';
    return 0;
}