简答题
偏难
#17222
试题名称 :划分字符串 时间限制 :3.0 s 内存限制 :512.0 MB
试题名称:划分字符串
时间限制:3.0 s
内存限制:512.0 MB


答案与解析
正确答案:<pre class="brush:python;toolbar:false;">n = int(input()) # 字符串长度
s = input().strip() # 原字符串
# a[k] 代表长度为k的合法无重复字符子串的价值,a[0]占位不用
a = [0] + list(map(int, input().split()))
# DP数组:f[i] 表示字符串前i个字符分割后的最大收益
f = [0] * (n + 1)
for i in range(1, n + 1):
# 存储当前末尾分段已出现过的字符
exist_chars = set()
# j从i向左枚举,最后一段从j到i(下标j-1 ~ i-1)
for j in range(i, 0, -1):
c = s[j - 1]
# 当前字符在末尾分段重复,不能继续往左拓展
if c in exist_chars:
break
exist_chars.add(c)
# 最后一段长度 len = i - j + 1
seg_len = i - j + 1
f[i] = max(f[i], f[j - 1] + a[seg_len])
print(f[n])</pre>
这道题暂未补解析。