Dayi Lin, Ph.D.

Senior Researcher, Data Science and Software Engineering

Tag: 算法

最小编辑距离 算法原理

问题 最小编辑距离 Minimum Edit Distance关于两个字符串s1,s2的差别,可以通过计算他们的最小编辑距离来决定。设A、B为两个字符串,狭义的编辑距离定义为把A转换成B需要的最少删除(删除A中一个字符)、插入(在A中插入一个字符)和替换(把A中的某个字符替换成另一个字符)的次数,用ED(A,B)来表示。直观来说,两个串互相转换需要经过的步骤越多,差异越大。例如 s1 = “12433” 和 s2 = “1233”;则可以通过在s2中间插入4得到12433与s1一致。即 d(s1,s2) = 1 (进行了一次插入操作) 性质 计算两个字符串s1+c1, s2+c2的编辑距离有这样的性质: 1. d(s1,””) = d(“”,s1) = |s1| d(“c1″,”c2”) = c1 == c2 ? 0 : 1; 2. d(s1+c1,s2+c2) = min( d(s1,s2)+ c1==c2 ? 0 : 1 , 1 + d(s1+c1,s2), 1 + d(s1,s2+c2) ); 第一个性质是显然的。第二个性质: 由于我们定义的三个操作来作为编辑距离的一种衡量方法,于是对c1,c2可能的操作只有: 1.

POJ-2240 解题报告

题意简述 输入货币名称以及货币间的汇率(A到B的汇率可能与B到A的不同),判断是否有可能实现套汇(即从某指定货币开始,通过一系列的货币兑换操作,最终换回某货币并实现盈利)。 问题有多组数据,对于每组数据,第一行代表货币类别数量,第二行起的n行为各货币名称;接下来一行是允许的兑换方式总数,而后每行有三个部分,第一个和第三个分别是原始货币和兑换后货币的名称,第二个是汇率。数据的输入以0结束。 对于每组数据,输出是否可能实现套汇(YES或NO)。

POJ-1125 解题报告

题意简述 股票经纪人之间的关系形成了一个有向关系网。每个股票经纪人向与他关联的另一个人传递一条谣言需要花费的时间各不相同。A向B传播谣言耗时并不一定等于B向A传播耗时。某经纪人收到谣言后会同时开始向他所有关联的经纪人传播谣言。给定股票经纪人之间的关系网以及每个经纪人向特定经纪人传播消息的耗时,问谣言从哪个股票经纪人开始传播能最快的使整个网所有人知道该谣言,并输出最短耗时。如果存在某经纪人无论如何无法得知该谣言,输出disjoint。

POJ-1062 解题报告

题意简述 你想娶酋长的女儿,但酋长要求你给一定数额金钱的聘礼。除了金钱外,酋长也允许你用部落里其他人的某物品加上一点钱作为聘礼。而其他人的物品也可以通过指定的另外一些人的某物品加上一些金钱获得。部落里的每个人有一个等级。你的整个交易过程涉及的人的等级只能在一个限定的差值内。问你最少需要多少金钱才能娶到酋长女儿。假定每个人只有一个物品。 例: 最高最低等级差不超过1,共4个物品 酋长的女儿    等级3     要求现金10000元     或甲的物品+8000元     或乙的物品+5000元 甲的物品     等级2     要求现金1000元      或丙的物品+200元 乙的物品        等级2     要求现金3000元      或丙的物品+200元 丙的物品        等级2     要求现金50元 在这个例子中,最少花费方案是:买丙的东西(50)换乙的东西(+200)换酋长女儿(+5000)一共5250元。

POJ-2253 解题报告

题意简述 湖中有N(2<=N<=200)块石头,标号从1到N。青蛙1在石头1上,青蛙2在石头2上。给定所有的石头坐标。青蛙1试图从石头1到石头2来找青蛙2,它可以经由任意石头组成的路径。在所有可能路径中找出一条路径,使其中最长的一步的长度小于其他路径中最长的一步的长度。 本题可以化简为,点1与点2间存在若干条路径,每条路径中都存在最长的一条边。找出一条路径使得该路径最长边的长度小于其他任意路径最长边。

POJ-1860 解题报告

题意简述 某城市有M(1<=M<=100)个货币兑换站,可以兑换N(1<=N<=100)种货币,每个兑换站只能互换两种货币,且汇率与手续费各不相同。某人初始时手中有V元货币S,问他是否有可能通过货币兑换,在最后换回货币S时实现盈利,有可能则输出YES,否则输出NO。

POJ-3259 解题报告

题意简述 农夫共有F(1≤F≤5)个农场,每个农场有N块田(1 ≤ N ≤ 500)和M条普通无向路(1 ≤ M ≤ 2500),走过这些路需要一定时间。同时还存在W条有向虫洞(1 ≤ W ≤ 200),走这些虫洞可倒流一定时间。问对于各个农场,农夫是否有可能从某点出发,回到原点时时间早于出发时间。每个农场输出一行。可能则输出YES,否则为NO。