TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2240
  • Problem
  • P2240最佳奖励加强版:最佳惩罚
    Limits : Time Limit : 1000 MS   Memory Limit : 65536 KB
    Description

    项链是小写字母组成的一个环。

    同一个字母的价值相同,一个回文串的价值是字母的价值总和,非回文串价值为0。

    你的任务是把项链切成两个非空字符串,总价值最大。

    Input Format

    有多组输入数据,
    第一行,一个整数T (1 ≤ T ≤ 10)表示测试数据的数目,对于每组测试数据:
    第一行,26个空格间隔的整数v1, v2, ..., v26 (0 ≤ vi ≤ 100, 1 ≤ i ≤ 26), 表示每种宝石的价值。
    接下来一行,一个由小写字母构成的长度不超过500000的字符串(至少三个字符),表示项链,26个字母代表26种宝石,'a'的价值是v1,'b'的价值是v2...'z'的价值是v26

    Output Format

    对于每组测试数据, 输出一行,一个整数,表示答案

    Sample Input

    2
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    aba
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    acacac

    Sample Output

    3
    4


    Source  2203加强版