fork download
copy 
  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         int n = sc.nextInt();
  7.         long[] b = new long[n + 1];
  8.         int k = sc.nextInt();
  9.  
  10.         for (int i = 1; i <= n; i++) {
  11.             b[i] = sc.nextLong();
  12.         }
  13.  
  14.         long[] dp = new long[n + 1];
  15.  
  16.         // Initialize dp array
  17.         for (int i = 1; i <= n; i++) {
  18.             dp[i] = Long.MAX_VALUE;
  19.         }
  20.  
  21.         // Starting conditions
  22.         dp[1] = 0; // Cost to reach the first stone is zero
  23.  
  24.         // Handle the case for the second stone
  25.         if (n >= 2) {
  26.             dp[2] = Math.abs(b[2] - b[1]); // Cost to reach the second stone
  27.         }
  28.  
  29.         // Calculate minimum costs for each stone
  30.         for (int i = 3; i <= n; i++) {
  31.             long mini = Long.MAX_VALUE;
  32.             for (int j = 1; j <= k && i - j >= 1; j++) {
  33.                 mini = Math.min(dp[i - j] + Math.abs(b[i] - b[i - j]), mini);
  34.             }
  35.             dp[i] = mini;
  36.         }
  37.  
  38.         System.out.println(dp[n]);
  39.     }
  40. }
  41.  
Success #stdin #stdout 0.14s 56640KB
comments (?)
stdin
copy 
10 4
40 10 20 70 80 10 20 70 80 60
stdout
copy 
40
https://ideone.com/ptWZPO
language:
Java (HotSpot 12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!