解题思路

• 问题抽象

  • 允许配对的仅限“同大小写且互补”的字母对：小写 (a,z)/(z,a), (b,y)/(y,b), ..., (m,n)/(n,m)；大写 (A,Z)/(Z,A), ..., (N,M)/(M,N)。
  • 互补条件等价于二者位置和为 27：若 pos(c) 为字母在字母表中的位置（不分大小写），则可配当且仅当二者同为小写或同为大写，且 pos(x) + pos(y) = 27。
  • 配对在环上不能相交，等价于“区间不交叉匹配”。

• 环转线的处理

题目内容

魔法项链是一个环形链条，上面串联着 $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)$ ;

• 每个宝石最多被选一次;

• 在环上，用弦连接每对宝石时，不得有两条弦相交(无交叉匹配)

对于每选中的括号对 $(s_1,s_2)$ ，你将获得分数 $pos(s_1)×pos(s_2)$ ，其中 $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$ 。