小欧有一个字符串，她要从字符串的开头走到字符串的结尾，初始时小欧在字符串开头。她每次可以花费”两个位置字母 ASCII 码值之差的绝对值”的代价走到下一个位置，或花费 “2 的位置距离减一次方”的代价走到下一个与此位置字母相同的位置。例如字符串 aba，小欧可以先花费 1 的代价从 ‘a’ 走到 ‘b’ 再花费 1 的代价从 ‘b’ 走到 ‘a’ ，也可以直接花费的代价直接从前面的 ‘a’ 走到后面的 ‘a’ （两个 ‘a’ 的距离为 2）。求小欧从字符串开头走到结尾需要花费的最小代价。

区块链毕设网qklbishe.com为您提供问题的解答

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

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

例如字符串 aba，小欧可以先花费 1 的代价从 ‘a’ 走到 ‘b’ 再花费 1 的代价从 ‘b’ 走到 ‘a’ ，也可以直接花费 $小欧有一个字符串，她要从字符串的开头走到字符串的结尾，初始时小欧在字符串开头。她每次可以花费"两个位置字母 ASCII 码值之差的绝对值"的代价走到下一个位置，或花费 "2 的位置距离减一次方"的代价走到下一个与此位置字母相同的位置。例如字符串 aba，小欧可以先花费 1 的代价从 'a' 走到 'b' 再花费 1 的代价从 'b' 走到 'a' ，也可以直接花费的代价直接从前面的 'a' 走到后面的 'a' （两个 'a' 的距离为 2）。求小欧从字符串开头走到结尾需要花费的最小代价。$ 的代价直接从前面的 ‘a’ 走到后面的 ‘a’ （两个 ‘a’ 的距离为 2）。

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

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])

58:39

以上就是关于问题小欧有一个字符串，她要从字符串的开头走到字符串的结尾，初始时小欧在字符串开头。她每次可以花费”两个位置字母 ASCII 码值之差的绝对值”的代价走到下一个位置，或花费 “2 的位置距离减一次方”的代价走到下一个与此位置字母相同的位置。
例如字符串 aba，小欧可以先花费 1 的代价从 ‘a’ 走到 ‘b’ 再花费 1 的代价从 ‘b’ 走到 ‘a’ ，也可以直接花费的代价直接从前面的 ‘a’ 走到后面的 ‘a’ （两个 ‘a’ 的距离为 2）。

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

欢迎关注区块链毕设网-
web3一级市场套利打新赚钱空投教程

区块链NFT链游项目方科学家脚本开发培训