Editorial for Atcoder Educational DP Contest B - Frog 2


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.

Author: 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;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.