2318 - 字母项链(necklace)

题目描述

小 W 有一个用大写字母串成的项链,有一天,他想把项链从中间某位置剪断,拉成一条直线后形成一个线性的字母串,其价值为每个字母的字典序位置 \times 位置号的和。

所谓字典序位置指该字母在 26 个字母表中排在第几个位置;位置号指该字母在字符串中排在第几个位置。

现在的问题是:该从哪里截断,才能让这个线性串的价值最大?

如:WJOI 组成的项链, ,可能的截断后的线性串有:

IW 中间截断,拉直后是 WJOI,价值为:23 \times 1+10 \times 2+15 \times 3+9 \times 4=124

JO 中间截断,拉直后是 OIWJ,价值为: 15 \times 1+9 \times 2+23 \times 3+10 \times 4=142

WJ 中间截断,拉直后是 JOIW,价值为:10 \times 1+15 \times 2+9 \times 3+23 \times 4=159

OI 中间截断,拉直后是 IWJO,价值为:9 \times 1+23 \times 2+10 \times 3+15 \times 4=145

其中最大的价值为:159

输入

一个只包含大写英文字母的字符串,最大长度不超过 100000

输出

一个整数,表示最大的价值。

样例

输入

WJOI

输出

159
说明

【数据范围】

10\% 的数据,串长=1

另外 10\% 的数据,串长=2

50\% 的数据,串长≤1000

100\%的数据:1≤串长≤100000

来源

2019 年武进区第 12 届程序设计比赛试题-小学组 T5

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 516
通过人数 236
金币数量 2 枚
难度 基础


上一题 下一题