Atcoder Educational DP Contest B - Frog 2

View as PDF
Submit solution
Points: 0.20 (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 các hòn đá thứ ~i+1~, ~i+2~ ~...~ ~i + K~. Chú sẽ mất 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 hai số nguyên dương ~N~ và ~K~ ~(2 \le N \le 10^{5}, 1 \le K \le 100)~, lần lượt là số lượng hòn đá và giới hạn nhảy của ếch.
  • 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
5 3
10 30 40 50 20
Output
30
Giải thích

Một đường đi tối ưu là: ~1 \rightarrow 2 \rightarrow 5~. Chi phí sẽ là ~|10 - 30| + |30 - 20| = 30~.

Sample 2

Input
3 1
10 20 10
Output
20
Giải thích

Một đường đi tối ưu là: ~1 \rightarrow 2 \rightarrow 3~. Chi phí sẽ là ~|10 - 20| + |20 - 10| = 20~.

Sample 3

Input
2 100
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 4

Input
10 4
40 10 20 70 80 10 20 70 80 60
Output
40
Giải thích

Một đường đi tối ưu là: ~1 \rightarrow 4 \rightarrow 8 \rightarrow 10~. Chi phí sẽ là ~|40−70|+|70−70|+|70−60|=40~.

Comments

Please read the guidelines before commenting.


  • 0
    hanguyen140210  commented on Jan. 6, 2026, 7:16 a.m.

    include<bits/stdc++.h>

    using namespace std;

    define vec vector

    define ll long long

    int i,j; int main(){ iosbase::syncwithstdio(0); cin.tie(0);cout.tie(0); int n,k;cin>>n>>k; vec<int>a(n),dp(n,INTMAX); for(int&x:a)cin>>x; dp[0]=0; for(i=0;i<n;i++){ for(j=1;j<=k;j++) if(i+j<n){ dp[i+j]=min(dp[i+j],dp[i]+abs(a[i]-a[i+j])); } else continue; } cout<<dp[n-1]; }


  • -6
    LVT_K66_TRANDUYBAO  commented on Oct. 12, 2025, 4:51 p.m.

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


  • 0
    hiephongbs89  commented on Aug. 18, 2025, 5:17 a.m.

    include <bits/stdc++.h>

    using namespace std;

    define ll long long

    const int maxn = 1000004; int f[maxn],b[maxn]; int main() { //freopen("DOANXE.INP","r",stdin); //freopen("DOANXE.OUT","w",stdout); iosbase::syncwith_stdio(false); cin.tie(NULL); int n , k; cin >> n >> k; int a[n]; for(int i = 0;i < n;i++){ cin >> a[i]; } f[0] = 0; for(int i = 1;i < n;i++){ f[i] = 1e9; for(int j = i - 1;j >= i - k;j--) { f[i] = min(f[i],f[j] + abs(a[i] - a[j])); } } cout << f[n - 1]; } ủa sao sai v ai chỉ giúp mình với .


  • 7
    ChiPhatNguyen  commented on Aug. 15, 2025, 4:20 p.m. ← edit 2

    Bài toán: Ếch nhảy qua các hòn đá Ý tưởng giải:

    • Gọi dp[i] là chi phí ít nhất để nhảy đến hòn đá thứ i
    • Trường hợp cơ sở:
      • dp[1] = 0
    • Công thức quy hoạch động: Với mỗi i (từ 2 đến n), ếch có thể nhảy từ bất kỳ hòn đá j (i-k<=j<i) Do đó: dp[i] = min( dp[j] + |hi - hj| ) với mọi j thỏa 1 ≤ j ≤ i-1 và (i-j<=k)
    • Kết quả cần tìm là dp[n]. Độ phức tạp:
    • Thời gian: O(n*k)
    • Bộ nhớ: O(n)

    code vi du : code


  • -12
    vutuankiet  commented on July 4, 2025, 3:24 p.m.

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


  • -4
    haoluu2009  commented on June 21, 2025, 3:02 p.m. ← edited

    cho e xin sol ạ


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

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


  • -9
    HoàngShine37  commented on July 17, 2024, 4:39 a.m. ← edited

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


  • -2
    Soab  commented on May 12, 2024, 8:28 a.m.

    ok


  • 4
    dangminh  commented on March 26, 2024, 4:59 p.m. ← edited

    sao lại là 1e9 mới ac v mn


    • 6
      tungdao123pzo  commented on May 23, 2024, 3:02 p.m.

      dp[i] có thể cộng dồn lên đến gần 1e9 thì để khỏi tạo 1e9 tính dp[i] = min(dp[i], giatri) cho de.


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

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


  • 3
    nhpuyen  commented on Feb. 26, 2023, 6:56 a.m.

    cho e hỏi tại sao đặt min 1e5 lại sai mà 1e9 lại đúng ạ. Với h[i] <= 1e4 mà.