Chú ếch và hòn đá 2

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Xem hướng dẫn

Thời gian:

Python 3 6.0s

Bộ nhớ:

Python 3 256M

Tác giả:

jumptozero

Dạng bài

Điểm: 350 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Có \(N\) hòn đá được đánh số \(1,2,3,...,N\). Với mỗi \(i(1\le i\le N)\), chiều cao của hòn đá thứ \(i\) là \(h_i\)

Có một con ếch ban đầu ở hòn đá \(1\). Nó lặp lại hành động sau với một số lần bất kì cho đến khi nó đến được hòn đá \(N\).

Nếu con ếch đang ở hòn đá \(i\), thì nó có thể nhảy sang hòn đá thứ \(i+1\) hoặc \(i+2\) hoặc ... hoặc \(i+K\) với chi phí là \(|h_i-h_j|\), trong đó \(j\) là vị trí nó muốn nhảy tới.

Tìm chi phí tối thiểu để nó đến được hòn đá thứ \(N\).

Input

Dòng thứ nhất chứa hai số nguyên \(N,K(2\le N\le 10^5,1\le K\le 100)\)
Dòng thứ hai chứa \(N\) số nguyên : \(h_1,h_2,...,h_N\) với \(1\le h_i\le 10^4\)

Output

In ra chi phí tối thiểu cần tìm

Example

Test 1

Input

5 3
10 30 40 50 20

Output

Note

Giải thích: Con ếch sẽ nhảy như sau: \(1\rightarrow 2 \rightarrow 5\), với chi phí là \(|10-30|+|30-20|=30\)

Bình luận

-1

def min_cost_to_reach_n(N, K, heights):

dp = [float('inf')] * (N + 1)
dp[1] = 0


for i in range(1, N + 1):
    for j in range(1, K + 1):
        if i + j <= N: 
            cost = abs(heights[i - 1] - heights[i + j - 1])
            dp[i + j] = min(dp[i + j], dp[i] + cost)

return dp[N]

N, K = map(int, input().split())
heights = list(map(int, input().split()))

print(min_cost_to_reach_n(N, K, heights))

3 bình luận nữa