3264 - 博物馆展览计划
题目描述
在一个古老的博物馆中，管理员们正在策划一个新的展览。在这个展览中，将展示一系列带有特殊图案的古代石板。每块石板上的图案都由小写字母 a 到 z 组成，每个字母代表不同的雕刻技艺难度和艺术价值。
给定一个长度为 n 的仅由小写字母组成的字符串 S，表示某块石板上现有的图案。管理员们可以在图案的任意位置插入最多 k 个小写字母，以增加这块石板的整体艺术价值。每个字母的价值由其在字母表中的位置决定，并且有一个具体的权重值 v。
具体来说，一个字符串 S 的价值定义为：v_1 \times 1 + v_2 \times 2 + ... + v_n \times n，其中 v_i 表示字母 S_i 的权重，1 \leq i \leq n。
现在，管理员们希望通过合理地插入字母，使得这块石板的整体价值最大化。请你帮助他们计算出最大可能的价值。
输入
第一行包含一个字符串 S，表示石板上现有的图案。
第二行包含一个整数 k，表示可以插入的小写字母数量。
第三行包含 26 个整数 v_a, v_b, ..., v_z，依次表示 a b c ... z 这 26 个字母，每个字母的权重。
输出
输出一个整数，表示通过插入字母后，石板图案的最大可能价值。
样例
输入
abc 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
输出
118
输入
defghi 3 1 6 5 5 3 3 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1
输出
179
输入
uvvwfutfrrsuyhggfigjhmhzecdoftxeljtthdpbqgxcobxdwhhsmixgxceleu 463 705 408 929 650 510 5 622 256 206 947 212 422 349 340 597 652 208 2 213 733 752 369 104 936 728 980
输出
134480697
说明
样例 1 解释
有 3 个字母构成的字符串 abc，可以在任意位置插入 1 个字母。
选择在最后插入字母 z，得到字符串 abcz，此时可以得到最大价值 =1\times1+2\times2+3\times3+26\times4=118。
数据范围
前 30\% 的测试点满足，S 的长度在 [1,5] 的范围内，k=1。
所有测试点满足，S 的长度范围 {[1,1000]} ，{0 \le k \le 10^3} ，{v_a∼v_z} 的取值范围 {[0,1000]} 。
标签
