Tóm tắt đề bài

Có \(N\) hòn đá với độ cao \(h_1, h_2, \dots, h_N\). Con ếch bắt đầu ở hòn đá \(1\) và muốn tới hòn đá \(N\). Từ hòn đá \(i\) nó có thể nhảy tới một trong các hòn đá \(i+1, i+2, \dots, i+K\), mỗi lần nhảy từ \(i\) tới \(j\) tốn chi phí \(|h_i - h_j|\).

Yêu cầu: tìm tổng chi phí nhỏ nhất để đi từ hòn đá \(1\) tới hòn đá \(N\).

Phân tích

• \(N \le 10^5\) khá lớn, nên không thể thử mọi đường đi.
• \(K \le 100\) nhỏ, gợi ý quy hoạch động với chuyển trạng thái xét tối đa \(K\) bước lùi.
• Đây là bài toán “đường đi tối ưu” theo thứ tự tăng chỉ số, nên có thể dùng DP 1 chiều:
  • Trạng thái phụ thuộc vào các trạng thái trước đó gần nhất.

Hướng giải quyết

Ý tưởng DP

Gọi \(dp[i]\) là chi phí tối thiểu để ếch đi tới hòn đá \(i\) (theo chỉ số \(0\)-based trong code, tương ứng hòn đá \(i+1\) trong đề).

• Cơ sở:
  • \(dp[0] = 0\) (đang ở hòn đá đầu tiên thì không tốn chi phí).
• Chuyển trạng thái:
  • Để tới \(i\), ếch có thể nhảy từ một hòn đá \(j\) bất kỳ sao cho \(i-K \le j < i\).
  • Khi đó:

Liên hệ với code AC đã cho

Code hiện thực đúng công thức trên:

• Khởi tạo dp với giá trị rất lớn inf.
• Đặt dp[0] = 0.
• Với mỗi \(i\) từ \(1\) đến \(N-1\), duyệt \(j\) từ \(i-1\) lùi về tới \(\max(0, i-K)\) và cập nhật:

dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j])).

Các lỗi hay gặp

• Quên giới hạn dưới của \(j\) là \(\max(0, i-K)\) sẽ dẫn đến truy cập chỉ số âm.
• Dùng int có thể vẫn đủ trong bài này, nhưng dùng long long an toàn hơn (code đã dùng ll).
• Nhầm chỉ số \(1\)-based và \(0\)-based: đề đánh số \(1..N\), code dùng \(0..N-1\).

Độ phức tạp

• Mỗi \(i\) duyệt tối đa \(K\) giá trị \(j\).
• Thời gian: \(O(NK)\), với \(N \le 10^5\), \(K \le 100\) là ổn.
• Bộ nhớ: \(O(N)\) cho mảng \(dp\) và \(h\).

Code tham khảo

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

#define ll long long
#define inf (ll)1e18
const int maxt = 2e5 + 36;

ll n, k, h[maxt];
vector<ll> dp(maxt, inf);

void solve() {
    cin >> n >> k;
    for (ll i = 0; i < n; i++) cin >> h[i];

    dp[0] = 0;
    for (ll i = 1; i < n; i++) {
        for (ll j = i - 1; j >= max(0LL, i - k); j--) {
            dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]));
        }
    }
    cout << dp[n - 1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    solve();
    return 0;
}