给出一个字符串,并且可以在字符串中更改至多Q个字母。您还会得到一个子字符串列表(每两个字符长),并带有相应的分数。字符串中的每个子字符串都会增加总分数。可获得的最高分数是多少?更改字符串的字母以获得最高分数
字符串长度< = 150,Q < = 100,子串<总数= 700
实施例:
字符串= bpdcg
Q = 2个
子串:
BZ - 得分:2
ZD - 得分:5
DM - 得分:7
纳克 - 分数:10
在这个例子中,可以实现的最大得分b更改“字符串中的“p”改为“z”,“c”改为“n”。因此,新的字符串为“bzdng”,它的得分为2 + 5 + 10 = 17
我知道,鉴于已经有字母改为一个字符串,比分可以在线性时间使用检查字典匹配算法,如aho-corasick(或复杂程度稍差的Rabin Karp)。但是,尝试每两个字母替换将花费太长时间,然后检查将花费太长时间。
我认为是向后工作,从给定的子构建理想的字符串,然后检查是否相差从原始字符串最多两个字符另一种可能的方法。但是,我不确定如何做到这一点,即使可以完成,我认为这也需要很长时间。
什么是最好的方式去做这件事?
String和Q的最大长度是多少? – 2014-10-28 02:55:12
@PhamTrung该字符串最多可以包含150个字符,Q可以最大为100 – 1110101001 2014-10-28 03:11:23
这看起来像一个背包问题。 – 2014-10-28 04:13:26