※ 引述《VictorHsieh (不要想太多 :))》之銘言：
: ※ 引述《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 國所需的路徑。
Please write down the recursion.
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.109.21.31