Submission #14453565

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys
sys.setrecursionlimit(10**6)
N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**9
dp = [INF] * N
def solve(n):
    if dp[n] < INF:
        return dp[n]
    if n == 0:
        dp[n] = 0
    elif n == 1:
        dp[n] = abs(h[0] - h[1])
    else:
        for i in range(1, K+1):
            if n - i < 0:
                break
            if dp[n - i] < INF:
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys
sys.setrecursionlimit(10**6)

N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**9
dp = [INF] * N

def solve(n):
    if dp[n] < INF:
        return dp[n]

    if n == 0:
        dp[n] = 0
    elif n == 1:
        dp[n] = abs(h[0] - h[1])
    else:
        for i in range(1, K+1):
            if n - i < 0:
                break
            if dp[n - i] < INF:
                cost = dp[n - i] + abs(h[n - i] - h[n])
            else:
                cost = solve(n - i) + abs(h[n - i] - h[n])
            dp[n] = min(dp[n], cost)

    return dp[n]

print(solve(N-1))

Submission Info

Judge Result