Hướng dẫn giải của Atcoder Educational DP Contest B - Frog 2


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: Duy_e

Độ phức tạp thời gian: ~O(NK)~

Để giải quyết bài này ta sẽ dùng quy hoạch động. Ta định nghĩa ~dp[i]~ là chi phí ít nhất để đến được hòn đá thứ ~i~.

  • Ban đầu, chú ếch ở hòn đá đầu tiên nên ta có: ~dp[1] = 0~
  • Để đến hòn đá ~i~ ta có thể đến được từ các hòn đá ~i-j~, ~\forall j \begin{cases} 1 \le j \le K \\ 1 \le i - j \end{cases}~
  • Cuối cùng, ta có ~dp[i]~ được tính theo công thức sau: ~dp[i] = \min\limits_{1 \leq j \leq K,\: 1 \leq i - j} \{ dp[i-j] + | h[i] - h[i-j] | \}~

Vì kết thúc ở hòn đá thứ ~N~ nên kết quả bài toán là ~dp[N]~.

Hướng dẫn cài đặt:

#include <iostream>
using namespace std;
const long long N = 2e5 + 5;
int dp[N], h[N], n, k;

int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; i ++)
        cin >> h[i];

    dp[1] = 0; 

    for (int i = 2; i <= n; i ++){

        int min_of_al_J = 1e9;

        for (int j = 1; j <= k; j ++)
            if (i - j >= 1)
                min_of_al_J = min(min_of_al_J, dp[i - j] + abs(h[i] - h[i - j]));

        dp[i] = min_of_al_J;
    }

    cout << dp[n];

    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.