#411. 回文串
回文串
题目描述
小 R 有一个长度为 的仅包含小写英文字母的字符串 。虽然 可能很长,但它由 个连续的段构成:第 段由 个小写英文字母 组成。将 段依次拼接就是 ,有 。相邻两段字符可以相同。
字符串反转后与原字符串相同,称为回文串,即对所有 均有 。
小 R 每次可以把某个位置的字符修改为任意小写英文字母。求最少修改多少个位置,才能使 成为回文串。
输入格式
第一行一个正整数 ,接下来 行每行一个正整数 和一个小写英文字母 。
原比赛文件名为 string.in。本 Hydro 版本采用标准输入输出。
输出格式
输出一个整数,表示最少修改次数。原比赛文件名为 string.out。
输入输出样例
3
2 a
2 b
1 c
2
2
2 a
3 a
0
6
1000000000 a
1000000000 a
1000000000 a
1000000000 b
1000000000 b
1000000000 b
3000000000
样例解释
样例 1 的字符串为 aabbc,可以修改两位得到 aabaa,最少修改次数为 2。样例 2 本身是回文串,不需修改。
数据范围
- ;
- ;
- 为小写英文字母。
| 测试点编号 | ||
|---|---|---|
原题题面另含文件形式的样例 4、5、6,所给文字未包含对应文件,故未列出。此数据包为自行生成的民间测试数据,不是官方测试数据。
相关
在下列比赛中: