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

-2

def min_cost_to_reach_end(N, K, heights):
import heapq

# Mảng dp để lưu trữ chi phí tối thiểu đến từng hòn đá
dp = [float('inf')] * N
dp[0] = 0  # Chi phí để đến hòn đá đầu tiên là 0

# Sử dụng hàng đợi ưu tiên (heap) để lấy hòn đá có chi phí nhỏ nhất
heap = [(0, 0)]  # (chi phí, vị trí)

while heap:
    current_cost, i = heapq.heappop(heap)

    # Nếu chi phí hiện tại lớn hơn chi phí đã lưu trữ, bỏ qua
    if current_cost > dp[i]:
        continue

    # Cập nhật chi phí cho các hòn đá có thể nhảy đến
    for jump in range(1, K + 1):
        j = i + jump
        if j >= N:
            break
        new_cost = dp[i] + abs(heights[i] - heights[j])
        if new_cost < dp[j]:
            dp[j] = new_cost
            heapq.heappush(heap, (new_cost, j))

# Chi phí tối thiểu để đến hòn đá cuối cùng
return dp[N-1]

Đọc đầu vào

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

Tính và in ra chi phí tối thiểu

print(min_cost_to_reach_end(N, K, heights))

0

hungthcsyl 3:01 p.m. 23 Tháng 7, 2024

https://oj.vnoi.info/problem/atcoder_dp_b

3

ngoquangvinhne 4:42 p.m. 19 Tháng 4, 2024

tham khảo https://www.ideone.com/vx5FgE
đừng chép code nhé.