時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
青蛙要從河左岸到右岸後再回左岸，兩岸相距 D。石頭按位置排成一直線，大石 B 可踩任意次，小石 S 最多只能踩一次，不能碰水。規劃往返路線，使其中最長的一跳盡可能短。
輸入格式
第一行 T（T < 100）。每筆先給 N（0 ≤ N ≤ 100）及 D（1 ≤ D ≤ 10^9），再給 N 個 Type-M 格式的石頭描述。Type 為 B 或 S，M 為距左岸的位置，0 < M < D，依 M 遞增排列。
輸出格式
每筆輸出 Case k: L，k 從 1 開始，L 為最小可能的最長跳躍距離。
題目來源：UVa 11157 — Dynamic Frog，CPE 歷屆試題。 原題：https://onlinejudge.org/external/111/11157.pdf
範例測資
範例輸入 1
3 1 10 B-5 1 10 S-5 2 10 B-3 S-6
範例輸出 1
Case 1: 5 Case 2: 10 Case 3: 7
請先登入後再提交程式碼
討論與題解
載入討論區…