作者pangfeng (Ikari Gendou)
站内ACMCLUB
标题Re: 讨论用 第二题
时间Sat Dec 14 17:39:27 2002
※ 引述《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