※ 引述《JonathanWang (小尹)》之銘言： : Online Judge 104 Problem 不同的國家中，彼此間貨幣的兌換會有匯差。有人想以從 s 國換成外幣，再換回 s國 的方式，來賺取這此差額。題目給定 n 個國家，以及他們彼此兌換的匯率。請找出在 n 次交換內，賺取倍率為 1.01 以上的金額。若無合乎此條件的解，則輸出沒有。 Solution 假設 N 為 n 個國家的集合，map(l,i,j)為長度（定義為兌換的次數）為 l 時，第 i 國幣兌至第 j 國幣間的匯率。對於 s 國（ s 屬於 N ），欲求出：長度為 l 時，從 s 國換至他國再換回 s 國，可換到的最大值。我們可以先找出長度為 l-1 時，從 s 國經 由 s 國以外的這些國家 t_1 .. t_{n-1}，再從 t_1 .. t_{n-1} 換回 s 國的最大值。 當路徑上為 l-1 時，換回 s 國的過程中，倍率都未超過 1.01，即可保證在路徑為 l-1 前，成功的兌換不會出現。若在長度為 l 時到達 1.01，即為其解之一。 題目要求列出兌換的過程，我們只需加一個表來記錄即可：path(l,i,j,k)為在路徑長 度為 l 時，從 i 國至 j 國所需的路徑。 --

※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw) ◆ From: 140.112.240.81