P1605 - [ECUST2018新生赛]超级回文串

内存限制：256 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：72 通过：31

“小了白了兔，白了又了白”，小花梨又哼起了这首被复读机追捧过的神曲。
突然，小花梨发现“白了又了白”是回文串，然后它就问小信息：“你知道什么是回文串吗？”
小信息说：“知道呀，回文串就是正着反着都是一样的字符串”。
“那你知道什么是超级回文串吗？”小花梨问道。
“emmmm，没听过，有这个吗？”小信息回答。
“hhh，超级回文串就是这个字符串的所有偶数长度的子串都是回文串。”
现在，小信息想把一个只含有小写字母，长度为n的字符串s修改成超级回文串
修改字母时，修改的代价是修改前后字母的ASCII码之差的绝对值。
例如将字母a修改成字母c，所需要的代价是abs(′a′−′c′)=2。
小信息想知道字符串s变成超级回文串的最小代价是多少？

第一行一个整数T，表示有T组数据，对于每组数据：
第一行为正整数n，表示字符串s的长度,第二行为字符串s
输入保证字符串s 只含有小写字母，不含其余任何字符。
(1≤T≤1000,1≤n≤100)

对于每一组数据，输出"Case x: ans"(不含引号)
x表示第x组测试数据，从1开始编号，ans表示最小的代价

2
10
aabbaaccaa
10
aaaaabbbbb

Case 1: 6
Case 2: 5

EFPC

1605: [ECUST2018新生赛]超级回文串

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签