5983: BZOJ1983:毛毛虫的伪装

Memory Limit:64 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

菜妈在你的帮助下解决了菜儿们的问题后,就到一边睡觉去了(咦?不是说菜妈是个勤劳的菜农麽?……)。此时,一只可爱的毛毛虫来到了菜园里,正在啃食菜妈的菜儿们…… 可是菜妈警觉性极高,一听到毛毛虫啃食菜儿们的声音,菜妈就醒了。然后以光速拿来了毛毛虫最害怕的武器——DDT。就在菜妈冲向毛毛虫的时候,毛毛虫忽然想起菜妈是信仰一个***教的,而该***教是崇尚对称之美的,于是毛毛虫决定变换成“对称毛毛虫”,这样菜妈就不会拿DDT来喷毛毛虫了。这只奇怪的毛毛虫的身上有2N个字母,这些字母排成一行。每次操作,毛毛虫只能把其中某个字母移动到另一个字母的前面或者后面。由于时间紧迫,毛毛虫必须用最少的操作步数使得自己变成“对称毛毛虫”。


输入格式

第一行一个正整数N。第二行为毛毛虫身上的2N个字母。


输出格式

输出毛毛虫需要的最少操作步数。


样例输入

4
aaabbbab

样例输出

2

【Data Range】
N<=500,000,所有字母均为小写字母。
数据保证有解。

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: