ZeroJudge 解題筆記：t166.青蛙跳石

作者：王一哲
日期：2026年11月3日


ZeroJudge 題目連結：t166.青蛙跳石

解題想法

每組測資第一列為兩個整數 $n ~(2 \leq n \leq 2 \times 10^5), k ~(0 \leq t \leq 1000)$，分別代表有 $n$ 個石頭，一次最多可以往前跳 $k$ 個石頭；第二列有 $n$ 個整數 $h_i ~(0 \leq h_i \leq 10^9)$，分別代表第 $i$ 個石頭的高度。從第 $i$ 個石頭跳到第 $j$ 個石頭需要的能量為 $| h_i - h_j|$。求從第 $0$ 個石頭跳到第 $n-1$ 個石頭需要的最低能量。

這題考動態規畫。開一個長度為 $n$ 的一維陣列 $dp$，$dp[i]$ 代表跳到第 $i$ 個石頭需要的最低能量，預設為無窮大，另外 $dp[0] = 0$。用兩層 for 迴圈更新 $dp$，外層 for 迴圈跑起點 $i = 0$ 到 $i = n-2$；內層 for 迴圈跑終點 $j = i+1$ 到 $j = min(i+k+1, n) - 1$；如果 $dp[i] + abs(hs[i] - hs[j]) < dp[j]$，找到新的最低成本，更新 $dp[j]$。最後答案在 $dp[n-1]$。

Python 程式碼

使用時間約為 12 ms，記憶體約為 9.6 MB，通過測試。

def solve():
    import sys
    from bisect import bisect_left

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        k = int(data[ptr + 1])
        ptr += 2
        hs = tuple(map(int, data[ptr : ptr + n]))
        ptr += n

        # dp[i] 代表跳到第 i 個石頭的最低總成本，預設為無窮大
        dp = [float('inf')] * n
        dp[0] = 0  # 起點，成本 0
        # 測試從第 i 個石頭往後跳到第 j 個石頭是否為新的最低總成本
        for i in range(n-1):
            for j in range(i+1, min(i+k+1, n)):
                dp[j] = min(dp[j], dp[i] + abs(hs[i] - hs[j]))
        # 答案在 dp[n-1]
        result.append(f"{dp[n-1]:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

使用時間約為 14 ms，記憶體約為 9.6 MB，通過測試。

while True:
    try:
        n, k = map(int, input().split())
        hs = tuple(map(int, input().split()))
    except EOFError:
        break
    
    # dp[i] 代表跳到第 i 個石頭的最低總成本，預設為無窮大
    dp = [float('inf')] * n
    dp[0] = 0  # 起點，成本 0
    # 測試從第 i 個石頭往後跳到第 j 個石頭是否為新的最低總成本
    for i in range(n-1):
        for j in range(i+1, min(i+k+1, n)):
            dp[j] = min(dp[j], dp[i] + abs(hs[i] - hs[j]))
    # 答案在 dp[n-1]
    print(dp[n-1])

C++ 程式碼

使用時間約為 1 ms，記憶體約為 3.6 MB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
typedef long long LL;
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k;
    while(cin >> n >> k) {
        vector<int> hs (n);
        for(int i = 0; i < n; i++) {
            cin >> hs[i];
        }

        // dp[i] 代表跳到第 i 個石頭的最低總成本，預設為無窮大
        vector<LL> dp (n, LLONG_MAX);
        dp[0] = 0;  // 起點，成本 0
        // 測試從第 i 個石頭往後跳到第 j 個石頭是否為新的最低總成本
        for(int i = 0; i < n-1; i++) {
            for(int j = i+1; j < min(i+k+1, n); j++) {
                dp[j] = min(dp[j], dp[i] + abs(hs[i] - hs[j]));
            }
        }
        // 答案在 dp[n-1]
        cout << dp[n-1] << "\n";
    }
    return 0;
}

C 語言程式碼

使用時間約為 2 ms，記憶體約為 4 MB，通過測試。

#include <stdio.h>
#include <limits.h>
#include <math.h>
#define min(a, b) ((a) < (b) ? (a) : (b))
typedef long long LL;

int main() {
    int n, k;
    while(scanf("%d %d", &n, &k) != EOF) {
        int hs[200000];
        for(int i = 0; i < n; i++) {
            scanf("%d", &hs[i]);
        }

        // dp[i] 代表跳到第 i 個石頭的最低總成本，預設為無窮大
        LL dp[200000];
        for(int i = 0; i < n; i++) {
            dp[i] = LLONG_MAX;
        }
        dp[0] = 0;  // 起點，成本 0
        // 測試從第 i 個石頭往後跳到第 j 個石頭是否為新的最低總成本
        for(int i = 0; i < n-1; i++) {
            for(int j = i+1; j < min(i+k+1, n); j++) {
                dp[j] = min(dp[j], dp[i] + abs(hs[i] - hs[j]));
            }
        }
        // 答案在 dp[n-1]
        printf("%lld\n", dp[n-1]);
    }
    return 0;
}