小欧的最短路

[编程题]小欧的最短路

热度指数：500 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小欧有一个字符串，她要从字符串的开头走到字符串的结尾，初始时小欧在字符串开头。

她每次可以花费"两个位置字母 ASCII 码值之差的绝对值"的代价走到下一个位置，或花费 "2 的位置距离减一次方"的代价走到下一个与此位置字母相同的位置。

例如字符串 aba，小欧可以先花费 1 的代价从 'a' 走到 'b' 再花费 1 的代价从 'b' 走到 'a' ，也可以直接花费 $2^1$ 的代价直接从前面的 'a' 走到后面的 'a' （两个 'a' 的距离为 2）。

求小欧从字符串开头走到结尾需要花费的最小代价。

输入描述:

第一行输入一个整数  。

第二行输入一个长度为  的仅由小写字母组成的字符串。

输出描述:

输出一个整数表示答案。

示例1

输入

3
aba

输出

说明

如题目描述。

算法知识视频讲解

Python

浅野君

大家都说简单DP会超时，然而我这个这么简单，也没超时诶。。。

n = int(input())
chs = input()

pos = 0
cost = [0] * n
for i in range(1,n):
    lft = cost[i-1] + abs(ord(chs[i]) - ord(chs[i-1]))
    idx = chs[:i].rfind(chs[i])
    if idx != -1:
        rgt = cost[idx] + 2**(i-1-idx)
    else:
        rgt = 10**6
    cost[i] = min(lft, rgt)
print(cost[-1])

发表于 2025-12-06 02:31:57 回复(0)