Atcoder Educational DP Contest A - Frog 1
Xem dạng PDF
Gửi bài giải
Điểm:
0,10 (OI)
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Người đăng:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Có ~N~ hòn đá, được đánh số từ ~1~ đến ~N~. Với mỗi chỉ số ~i~ ~(1 \le i \le N)~, độ cao của hòn đá thứ ~i~ là ~h_{i}~
Ban đầu, có một chú ếch đang ngồi ở hòn đá thứ nhất và chú sẽ thực hiện liên tục một loạt các hành động sau:
- Nếu chú đang ngồi ở hòn đá ~i~ chú có thể nhảy đến hòn đá thứ ~i+1~ hoặc ~i+2~. Chú sẽ mất chi phí khi nhảy là ~|h_{i} - h_{j}|~ với ~j~ là hòn đá mà chú ếch nhảy đến.
Bạn hãy giúp chú ếch tìm chi phí tối thiểu để nhảy từ hòn đá thứ nhất đến hòn đá thứ ~N~ nhé.
Input
- Dòng đầu tiên của dữ liệu vào chứa số nguyên dương ~N~ ~(2 \le N \le 10^{5})~, là số lượng hòn đá.
- Dòng thứ hai gồm ~N~ số nguyên ~h_{i}~ ~(1 \le i \le N, 1 \le h_{i} \le 10^{4})~, là độ cao của hòn đá thứ ~i~.
Output
- Gồm một số nguyên, là chi phí ít nhất để nhảy từ hòn đá thứ nhất đến hòn đá thứ ~N~.
Sample 1
Input
4
10 30 40 20
Output
30
Giải thích
Một đường đi tối ưu là: ~1 \rightarrow 2 \rightarrow 4~. Chi phí sẽ là ~|10 - 30| + |30 - 20| = 30~.
Sample 2
Input
2
10 10
Output
0
Giải thích
Một đường đi tối ưu là: ~1 \rightarrow 2~. Chi phí sẽ là ~|10 - 10|= 0~.
Sample 3
Input
6
30 10 60 10 60 50
Output
40
Giải thích
Một đường đi tối ưu là: ~1 \rightarrow 3 \rightarrow 5 \rightarrow 6~. Chi phí sẽ là ~|30−60|+|60−60|+|60−50|=40~.
Bình luận
Công thức:
bài này dùng quy hoạch động được không mọi người?
n = int(input().strip()) a = list(map(int, input().strip().split())) p = [0] * (n + 1) p[2] = abs(a[0] - a[1]) for i in range(3, n + 1): p[i] = min(p[i - 1] + abs(a[i - 1] - a[i - 2]),p[i - 2] + abs(a[i - 1] - a[i - 3])) print(p[n])
hello
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
hello
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
ok :v:
Giống editorial nhưng mình code theo đệ quy cho dễ hình dung hơn.
https://github.com/Clitch01/DSA-/blob/master/Dynamic%20Programming%20Problems/A_Frog_1.cppBình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.