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

Xem PDF




Thời gian:
Python 3 6.0s
Bộ nhớ:
Python 3 256M

Tác giả:
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

\(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\)\(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
30
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

  • dancoder 1:45 p.m. 10 Tháng 3, 2025

    include <bits/stdc++.h>

    using namespace std;

    define int long long

    const int N = 2e5;
    const int F = 1e16;
    int h[N], dp[N];

    signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int n, k ; cin >> n >> k;
    for (int i = 1 ; i <= n ; i++){
    cin >> h[i] ; dp[i] = F;
    }
    
    dp[1] = 0;
    
    for (int i = 1; i < n; i++){
        for (int j = i + 1; j <= min(i + k, n) ; j++){
            dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));
        }
    }
    return cout << dp[n],0;
    

    }

    • kurodarker0 6:24 p.m. 18 Tháng 10, 2024

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

      • vietnammuonnam_mvn 6:18 p.m. 27 Tháng 8, 2024

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

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

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