Atcoder Educational DP Contest A - Frog 1

View as PDF
Submit solution
Points: 0.10 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout
Suggester:
Duy_e
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
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~.

Comments

Please read the guidelines before commenting.


  • 0
    Vinh9699  commented on April 22, 2025, 1:54 p.m.

    Công thức:

    DP[i] = min(abs(List[i - 1] - List[i]) + DP[i-1], abs(List[i - 2] - List[i])+ DP[i-2]);


  • -3
    iphone2207_  commented on Jan. 19, 2025, 11:09 a.m.

    bài này dùng quy hoạch động được không mọi người?


  • -4
    chuthang050520008  commented on Dec. 2, 2024, 6:59 a.m.

    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])


  • -2
    iphone2207_  commented on Oct. 30, 2024, 11:43 a.m.

    hello


  • -13
    khiemgia1105  commented on Oct. 4, 2024, 7:47 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -29
    jard  commented on Sept. 23, 2024, 2:57 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -9
    bquanghien1902  commented on Sept. 4, 2024, 7:33 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -4
    nb_truonghansieu_legiabao  commented on July 20, 2024, 3:24 p.m. ← edit 5

    hello


  • -11
    HoàngShine37  commented on July 17, 2024, 4:29 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -33
    jard  commented on April 27, 2024, 9:00 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -1
      MalazeKL  commented on April 28, 2024, 2:33 p.m.

      ok :v:


  • 2
    Nguyen_le2632007  commented on April 18, 2024, 11:52 a.m. ← edited

    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.cpp


  • -31
    khoihk20  commented on Sept. 29, 2023, 2:53 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -49
    nthquan_1505  commented on March 30, 2023, 4:22 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -73
    itk11_thanhbinh  commented on Jan. 11, 2023, 7:39 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.