ZeroJudge 解題筆記：b595. Special Touring Car Racing

作者：王一哲
日期：2025年7月29日


ZeroJudge 題目連結：b595. Special Touring Car Racing

解題想法

依序掃過 i = 1 ~ n 站，先計算從起點直接開到第 i 站的成本，再用另一層 for 迴圈，計算以 j = 1 ~ i-1 站為前一個停靠站到第 i 站的成本，更新第 i 站最低成本及前一個停靠站。最後再從終點往起點找出各停靠站的編號，將編號反向輸出。

Python 程式碼

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

import sys

for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)  # 讀取 n
    if n == 0: break  # 如果 n 等於 0 中止迴圈
    stop = [0] + list(map(int, sys.stdin.readline().split()))  # 讀取停靠站位置，加入 stop[0] = 0 
    cost = [float('inf')]*(n+1)  # 移動到第 i 站的成本，預設為極大的值
    prev = [0]*(n+1)  # 移動到第 i 站之前停靠的前一站
    for i in range(1, n+1):  # 依序檢查第 1 ~ n 站
        cost[i] = min(cost[i], (200 - stop[i])**2)  # 計算由開頭直接走到第 i 站的成本
        for j in range(1, i):  # 依序檢查由第 1 ~ i-1 站走到第 i 站的成本
            val = cost[j] + (200 - (stop[i] - stop[j]))**2
            if val < cost[i]:  # 如果 val 小於 cost[i] 目前的值
                prev[i] = j; cost[i] = val  # 更新 prev[i] 為 j、 cost[i] 為 val
    ### end of for loop ###
    ans = [n]  # 答案，先加入終點 n
    idx = n  # 由 prev 讀取資料的索引值
    while prev[idx] != 0:  # 如果 prev[idx] 不等於 0 繼續執行
        ans.append(prev[idx])  # 將 prev[idx] 加入 ans
        idx = prev[idx]  # 更新 idx 為 prev[idx]
    print(*([0] + ans[::-1]))  # 反序列印

C++ 程式碼

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

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    const int inf = 1000000000;
    int n;
    while(scanf("%d", &n) != EOF && n != 0) {  // 讀取 n
        // 停靠站位置，移動到第 i 站的成本，移動到第 i 站之前停靠的前一站
        vector<int> stop (n+1, 0), cost (n+1, inf), prev (n+1, 0);  // 讀取停靠站位置，加入 stop[0] = 0 
        for(int i=1; i<=n; i++) scanf("%d", &stop[i]);
        for(int i=1; i<=n; i++) {  // 依序檢查第 1 ~ n 站
            cost[i] = min(cost[i], (200 - stop[i])*(200 - stop[i]));  // 計算由開頭直接走到第 i 站的成本
            for(int j=1; j<i; j++) {  // 依序檢查由第 1 ~ i-1 站走到第 i 站的成本
                int val = cost[j] + (200 - (stop[i] - stop[j]))*(200 - (stop[i] - stop[j]));
                if (val < cost[i]) { //# 如果 val 小於 cost[i] 目前的值
                    prev[i] = j; cost[i] = val;  // 更新 prev[i] 為 j、 cost[i] 為 val
                }
            }
        }
        vector<int> ans = {n};  // 答案，先加入終點 n
        int idx = n;  // 由 prev 讀取資料的索引值
        while(prev[idx] != 0) {  // 如果 prev[idx] 不等於 0 繼續執行
            ans.push_back(prev[idx]);  // 將 prev[idx] 加入 ans
            idx = prev[idx];  // 更新 idx 為 prev[idx]
        }
        ans.push_back(0);
        int m = (int)ans.size();
        for(int i=m-1; i>0; i--) printf("%d ", ans[i]);
        printf("%d\n", ans[0]);
    }
    return 0;
}