我要招人

去企业版

首页 > 试题广场 >

小欧的最短路

[编程题]小欧的最短路

热度指数：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)

keff

对于每个位置i：
如果直接从i-1位置走过来： $dp[i] = dp[i-1] + |s[i] - s[i-1]|$
如果存在前面相同字符的位置k： $dp[i] = min(dp[i], dp[k] + 2^{i-k-1})$
使用一个数组记录每个字符出现的所有位置，方便快速查找前面相同字符的位置

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = "&" + s;
    vector<long long> dp(n + 1);
    vector<vector<int>> val(28, vector<int>(0));
    for (int i = 1; i <= n; i++) {
        val[s[i] - 'a' + 1].push_back(i);
    }
    int cnt[28] = {0};
    dp[1] = 0;
    cnt[s[1] - 'a' + 1]++;
    for (int i = 2; i <= n; i++) {
        if (cnt[s[i] - 'a' + 1] == 0)
            dp[i] = dp[i - 1] + abs(s[i] - s[i - 1]);
        else {
            long long k = val[s[i] - 'a' + 1][cnt[s[i] - 'a' + 1] - 1];
            if ((i - k - 1) <= 32)
                dp[i] = min(dp[k] + (1ll << (i - k - 1)), dp[i - 1] + abs(s[i] - s[i - 1]));
            else dp[i] = dp[i - 1] + abs(s[i] - s[i - 1]);
        }
        cnt[s[i] - 'a' + 1]++;
    }
    cout << dp[n] << endl;
}

编辑于 2025-06-10 21:10:39 回复(0)

纠结的安迪在刷代码

n = int(input())
s = input()
if n == 1:
    print(0)
else:
    dp = [float('+inf')] * n
    dp[0] = 0
    for i in range(1,n):
        for j in range(max(0,i-9),i):
            if s[j] == s[i]:
                dp[i] = min(dp[i],dp[j]+2**(i-j-1))
        dp[i] = min(dp[i],dp[i-1]+abs(ord(s[i])-ord(s[i-1])))
    print(dp[-1])

可以利用条件优化。指数函数增长很快。2**（x-1）>25*x的最小x为9。复杂度O(N)。大约扫了10次表格。

编辑于 2025-05-26 18:02:50 回复(0)

饿不死就行了

用python写的会超时，有大佬发一下python的吗，他这个测试用例太多了。

发表于 2025-05-02 22:17:40 回复(0)

湮堙

n = int(input())
s = input()
n = len(s)
dp = [float('inf')] * n
dp[0] = 0
dmap = {}
dmap.setdefault(s[0],[0])
for i in range(1,n):
    if s[i] not in dmap:
        dmap.setdefault(s[i],[i])
        dp[i] = min(dp[i],dp[i-1]+abs(ord(s[i])-ord(s[i-1])))
    else:
        tmp = dp[i-1]+abs(ord(s[i])-ord(s[i-1]))
        for j in dmap[s[i]]:
            dp[i] = min(dp[i],tmp,dp[j]+pow(2,i-j-1))
        dmap[s[i]].append(i)
# print(dmap)
# print(dp)
print(dp[-1])

简单动归会超时

from collections import deque

n = int(input())
s = input()
n = len(s)

dp = [float('inf')] * n
dp[0] = 0
dmap = {}

# 使用 deque 来优化状态转移
dmap.setdefault(s[0], deque([0]))

for i in range(1, n):
    dp[i] = dp[i - 1] + abs(ord(s[i]) - ord(s[i - 1]))

    # 如果之前有相同的字符出现过
    if s[i] in dmap:
        # 通过 deque 来保持可能的最小值位置
        while dmap[s[i]] and dp[dmap[s[i]][0]] + pow(2, i - dmap[s[i]][0] - 1) >= dp[i]:
            dmap[s[i]].popleft()

        for j in dmap[s[i]]:
            dp[i] = min(dp[i], dp[j] + pow(2, i - j - 1))

    dmap.setdefault(s[i], deque()).append(i)

print(dp[-1])

发表于 2025-02-14 18:58:39 回复(0)

提交观点

问题信息

难度：

5条回答 45收藏 770浏览

小欧的最短路

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题