圣殿战士是源自圣骑士的特殊战士类别,擅长神圣魔法。然而,圣骑士要达到圣殿级别,他们必须能够构造特殊法术。每个咒语必须是回文,这意味着向前和向后读取时它是相同的字符串。构建新法术的成本基于最终法术中出现的符文对成本(相邻字母的成本)。输入中未出现的符文对不允许出现在最终咒语中。法术的总成本是该法术中每次符文对出现时该法术中所有符文对成本的总和。
例如,如果咒语是
,那么成本就是abbaacaabba.
的成本总和ab + ba + ac + ca + ab + ba.
确定制作一个给定长度的新 Paladrome 咒语的最小成本。
输入:
输入的第一行包含两个整数 n (1 ≤ n ≤ 676) 和 k (2 ≤ k ≤ 100),其中 n 是符文对的数量,k 是符文(即字母)中所需的拼写长度。接下来的n行中的每一行都包含一个字符串s(s恰好由两个小写字母组成,可以相同或不同)和一个整数c(1≤c≤100),其中字符串s是一个符文对, c 是该符文对的成本。所有符文对都是不同的。输出:
输出一个整数,这是从给定符文构建长度为 k 的咒语的最小可能成本,如果不可能,则输出 -1。输入示例:
5 9 ab 4 ba 1 bd 3 db 100 bc 4
输出示例:
20
我无法理解这个问题,我不知道从哪里开始
侧边栏:这对我来说很有趣(作为一个 Python 新手和一个不太新手的 Fantasysta)。对于这个问题或来源我可以得到更多这样的问题吗?
问题解决方案:不是一个真正的解决方案,我可能会被否决,但我现在正在研究这个,我已将其分成几个子功能,从外到内工作。我想说你可以这样做与您的问题“了解从哪里开始”相同:
rune_cost = {
"ab" : 4
"ba" : 1
}
,正如我从你的例子中看到的-
但是,
本例中的拼写长度为 11,但符文对应该是两个字符?我可能误解了这个问题 - 相邻字母对是否应该不重叠(在这种情况下,成本应该是 ab + ba + ac + aa + bb + a?”)或者应该是(在这种情况下,成本应该是 ab + bb + ba + aa....+ bb + ba)。如果是任何一种情况,此函数可以使用正在创建回文的拼写_append()的输出来检查用户输入的长度、对等。您能澄清一下吗?
抱歉,我的是 WIP,我是 Python 新手。如果您面临着如您所说的不知道从哪里开始的问题,这是我的方法,我将其分解为更小的问题正在使用硬编码的候选输入进行测试,看看代码是否有效。干杯!