Editorial for Atcoder Educational DP Contest A - Frog 1


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(N)~

Để 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~. Dễ thấy để đến được hòn đá thứ ~i~, ta chỉ có thể nhảy từ :

  • Hòn đá thứ ~i - 1~ với ~( 1 < i \le N)~.
  • hòn đá thứ ~i - 2~ với ~( 2 < i \le N)~.

Vì chú ếch bắt đầu từ hòn đá đầu tiên nên: ~dp[1] = 0~. Từ đây, để đến được hòn đá thứ ~2~ ta có thể nhảy từ hòn đá đầu tiên ~\Rightarrow dp[2] = dp[1] + |h[2] - h[1]|~. Tính trước ~dp[1]~ và ~dp[2]~ ta có:

  • ~\forall i, 2 < i \le N , dp[i] = min(dp[i-1] + |h[i] - h[i-1]|, dp[i-2] + |h[i] - h[i-2]|)~

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;

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

    dp[1] = 0; dp[2] = abs(h[1] - h[2]);

    for (int i = 3; i <= n; i ++)
        dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]));

    cout << dp[n];

    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.