※ 引述《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