\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.5}}}}}\)

\(\color{#ff0000}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{#ff0000}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{#ff0000}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}\) ở đây

\(\color{#300000}{\text{Hint 1 <Cày trâu> <Quay lui>}}\)

• Từ vị trí \(x\) thử đi từng hòn đá ở vị trí \(x + 1\), \(x + 2\), \(\dots\), \(x + k\) và cộng vào kết quả

Vì tại mỗi ô có k lựa chọn, nên độ phức tạp sẽ là \(O(k^n)\)

Bạn có thể cải tiến bằng tham lam hoặc nhánh cận hoặc 2 cách dưới

\(\color{#300000}{\text{Hint 2 <Đệ quy có nhớ>}}\)

• Giống cách trên nhưng mình thêm nhớ vào 😃

• Gọi \(dp(i)\) là kết quả của bài toán con xuất phát từ điểm \(i\), là chi phí tối thiểu di chuyển \(i \rightarrow n\)

Khi \(i\) đi đến \(n\) thì chi phí là \(abs(a[n] - a[n]) = 0\)

Khi \(i\) đi đến \(i + 1 \leq n\) thì chi phí là \(dp(i + 1) + abs(a[i] - a[i + 1])\)

Khi \(i\) đi đến \(i + 2 \leq n\) thì chi phí là \(dp(i + 2) + abs(a[i] - a[i + 2])\)

...

Khi \(i\) đi đến \(i + k \leq n\) thì chi phí là \(dp(i + k) + abs(a[i] - a[i + k])\)

Kết quả của \(dp(i)\) là chi phí nhỏ nhất trong k cách trên

• Kết quả của bài toán là \(dp(1)\) với độ phức tạp thời gian \(O(n \times k)\)

\(\color{#300000}{\text{Hint 3 <Quy hoạch động>}}\)

• Gọi \(dp[i]\) là chi phí tối thiểu để di chuyển từ viên đá \(1 \rightarrow i\)

Khi \(i = 1\) thì \(dp[i] = a[1] - a[1] = 0\)

Nếu ô hiện tại xuất phát từ \(1 \leq i - 1\) thì kết quả là \(dp[i - 1]\) thêm với chi phí \(abs(a[i] - a[i - 1])\)

Nếu ô hiện tại xuất phát từ \(1 \leq i - 2\) thì kết quả là \(dp[i - 2]\) thêm với chi phí \(abs(a[i] - a[i - 2])\)

...

Nếu ô hiện tại xuất phát từ \(1 \leq i - k\) thì kết quả là \(dp[i - k]\) thêm với chi phí \(abs(a[i] - a[i - k])\)

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

\(dp[i] = 0\), với i = 1

\(dp[i] = abs(a[i] - a[i - j])\), với \(i \geq 2, j \in [1..k], i > j\)

• Kết quả bài toán là \(dp[n]\) với độ phức tạp thời gian \(O(n \times k)\)

\(\color{#009933}{\text{Preference Accepted Code }}\): Quy hoạch động

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n \times k)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n)\ \color{#7f5f3f}{\text{memory}}}}\)

/// Luu y code tham khao dung [0, n) thay vi [1, n]
void minimize(int &a, int b) { a = min(a, b); }
int main()
{
    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (int &x : a) cin >> x;

    vector<int> dp(n, 0);
    for (int i = 1; i < n; ++i)
    {
        dp[i] = dp[i - 1] + abs(a[i] - a[i - 1]);
        for (int j = i - 2; j >= max(0, i - k); --j)
            minimize(dp[i], dp[j] + abs(a[i] - a[j]));
    }

    cout << dp.back();
    return 0;
}

\(\color{#9000ff}{\text{<Question>}}\)

• Liệu bạn có thể giải này trực tiếp (vừa nhận \(a[i]\) là tính được \(dp[i]\)) với bộ nhớ \(O(k)\) ?