#P14075. [GESP202509 六级] 划分字符串
[GESP202509 六级] 划分字符串
题目描述
小 A 有一个由 个小写字母组成的字符串 。他希望将 划分为若干个子串,使得子串中每个字母至多出现一次。例如,对于字符串 street
来说,str + e + e + t
是满足条件的划分;而 s + tree + t
不是,因为子串 tree
中 e
出现了两次。
额外地,小 A 还给出了价值 ,表示划分后长度为 的子串价值为 。小 A 希望最大化划分后得到的子串价值之和。你能帮他求出划分后子串价值之和的最大值吗?
输入格式
第一行,一个正整数 ,表示字符串的长度。
第二行,一个包含 个小写字母的字符串 。
第三行, 个正整数 ,表示不同长度的子串价值。
输出格式
一行,一个整数,表示划分后子串价值之和的最大值。
6
street
2 1 7 4 3 3
13
8
blossoms
1 1 2 3 5 8 13 21
8
提示
对于 的测试点,保证 。
对于所有测试点,保证 ,。