frog2

Frog 2

يوجد \(N\) حجرًا مرقّمة \(1, 2, \dots, N\). ارتفاع الحجر رقم \(i\) هو \(h_i\). يقف ضفدع على الحجر \(1\). من الحجر \(i\) يمكنه القفز إلى أي حجر من الأحجار \(i + 1, i + 2, \dots, i + K\). القفزة من الحجر \(i\) إلى الحجر \(j\) تكلّف \(|h_i - h_j|\).

أوجد أقل تكلفة كلية ليصل الضفدع إلى الحجر \(N\).

القيود:

\(2 \le N \le 10^5\)
\(1 \le K \le 100\)
\(1 \le h_i \le 10^4\)

الإدخال:

السطر الأول: عددان صحيحان \(N\) و \(K\).
السطر الثاني: \(N\) عددًا \(h_1, h_2, \dots, h_N\).

المخرجات:

عدد صحيح واحد — أقل تكلفة كلية.

مثال:

الإدخال:

5 3
10 30 40 50 20

المخرجات:

(يقفز الضفدع \(1 \to 2 \to 5\)، بتكلفة \(20 + 10 = 30\).)

الحل

هذه المسألة هي Frog 1 مع قفزات أطول. نستخدم الحالة نفسها:

\(dp_i\) = أقل تكلفة للوصول إلى الحجر \(i\) (الأحجار مرقّمة من \(0\) في الكود).

القفزة الأخيرة إلى الحجر \(i\) تأتي من أحد الأحجار \(i - K, \dots, i - 1\) (الموجودة فقط)، لذلك

\(dp_i = \min\limits_{\max(0, i - K) \le j < i} \left( dp_j + |h_i - h_j| \right)\)

مع الحالة الأساسية \(dp_0 = 0\). نحسب القيم بترتيب تصاعدي للعدد \(i\)، لأن كل قيمة تستخدم مواقع أصغر فقط.

يوجد \(N\) حالة، وكل حالة تفحص \(K\) انتقالًا على الأكثر، لذلك التعقيد الزمني \(O(N \cdot K)\)، أي \(10^7\) عملية على الأكثر.

#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;

int h[100000];
int dp[100000];  // dp[i] = minimum cost to reach stone i

int main() {
    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        dp[i] = 2000000000;
        // the last jump comes from one of the stones i - k, ..., i - 1
        for (int j = max(0, i - k); j < i; j++) {
            dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]));
        }
    }

    cout << dp[n - 1] << "\n";
}