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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Độ 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