※ 引述《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 國所需的路徑。
map(l,s,d) = max( map(l-1,s,t) + map(1,t,d) for t in N )
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.240.81