P3378.第3题-魔法项链上的宝石
题目内容
魔法项链是一个环形链条，上面串联着 n 个宝石，每个宝石上刻着一个英文字母。
你可以选择若干对宝石，使得:
-
每对宝石刻的字母恰好是一个字母括号对，具体为小写对 (a,z),(z,a),(b,y),(y,b),...,(m,n),(n,m);
-
或大写对 (Z,A),(A,Z),(Y,B),(B,Y),⋅.⋅,(N,M),(M,N) ;
-
每个宝石最多被选一次;
-
在环上，用弦连接每对宝石时，不得有两条弦相交(无交叉匹配)
对于每选中的括号对 (s1,s2) ，你将获得分数 pos(s1)×pos(s2) ，其中 pos 表示字母在字母表中的位置(例如 pos(a)=pos(A)=1,...,pos(z)=pos(Z)=26 ) 。请计算能够获得的最大总分。
【名词解释】
- 环上无交叉匹配：环上无交叉匹配指将环上编号为 1,2,...,n 的宝石依次排列成圆，将每对宝石 (i,j) 之间连一条直弦，要求不存在两条弦在内部相交。
输入描述
第一行输入一个整数 n(1≤n≤500)，表示宝石的数量。
第二行输入一个长度为 n 、仅由大小写英文字母构成的循环字符串 s ，第 i 个字符表示环上第 i 个宝石的字母。
输出描述
输出一个整数，表示在环上选择无交叉匹配后能够获得的最大总分。
样例1
输入
6
azbyxb
输出
76
说明
在这个样例中，环上宝石依次为
-
a(1),z(2),b(3),y(4),x(5),b(6);
-
可选的无交叉匹配为 (1,2) 得 1×26 和 (3,4) 得 2×25 ;
-
总分 1×26+2×25=26+50=76 。
样例2
输入
4
AZaz
输出
52
说明
在这个样例中：
-
匹配 (1,2) 为 (A,Z) 得分 1×26=26 ；
-
匹配 (3,4) 为 (a,z) 得分 1×26=26 ;
-
两条弦不交叉，总分 26+26=52 。
