首页 > 试题广场 >

回文

[编程题]回文

热度指数：1 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

字符串 S 只包含小写英文字母。有四种操作，每次操作你可以选择其中一种：

删除字符串的第一个字母。
删除字符串的最后一个字母。
在字符串的头部添加任意一个你想要的字母。
在字符串的尾部添加任意一个你想要的字母。

删除一个第 i 种英文字母需要的花费是 A_i，添加一个第 i 种英文字母的花费是 B_i。
请问将字符串 S 变成回文串需要的最小花费是多少？

输入描述:

第一行输入一个字符串 S。
接下来 26 行，每行输入两个正整数 A_i 和 B_i，表示删除一个第 i 种字符所需的花费以及添加一个第 i 种字符所需的花费。
1≤ |S| ≤ 10⁵ 且字符串 S 中只包含小写英文字母.
1≤ A_i,B_i≤ 10⁹.

输出描述:

输出一个正整数，表示把字符串 S 变成一个回文串的最小花费。

示例1

输入

输出

算法知识视频讲解

buerdepepeqi

发表于 2019-08-08 10:22:01

题意:给你一个字符串，你可以进行如下操作删除字符串的第一个字母。删除字符串的最后一个字母。在字符串的头部添加任意一个你想要的字母。在字符串的尾部添加任意一个你想要的字母。每次操作的代价是根据字母来定的，问你将字符串变成一个回文串所需要的最小花费题解：将串变成回文串，一定是以串中某个位置为回文中心，然展开全文