一句话题意: 每个字母添加和删除都相应代价 (可以任意位置 增加 / 删除), 求把原串变成回文串的最小代价
Description
保持对所有奶牛的跟踪是一项棘手的任务, 因此农场主约翰已经安装了一个系统来实现自动化. 他在每头奶牛身上安装了一个电子 ID 标签, 系统将在奶牛经过扫描仪时读取. 每个 ID 标记是从字母表中提取的一个字符串.
奶牛, 它们是淘气的动物, 有时试图通过倒着走来欺骗系统. 如果一头奶牛的 ID 是 "abcba", 那么无论她怎么走, 它都能读到同样的东西, 而拥有 "abcb" 的奶牛可能会注册为两个不同的 ID("abcb" 和 "bcba").
FJ 希望改变奶牛的 ID 标签, 这样无论奶牛走过哪个方向, 他们都能读到同样的标签. 例如,"abcb" 可以通过在末尾添加 "a" 来改变, 从而形成 "abcba", 这样 ID 就会是一个回文串. 更改 ID 的其他一些方法包括将三个字母 "bcb" 添加到 "abcb" 的开始, 以获得 ID"bcbabcb" 或删除字母 "a" 以产生 ID"bcb". 我们可以在字符串中的任意位置添加或删除字符, 其长度比原来的字符串长或短.
不幸的是, ID 标签是电子信息, 每个字符插入或删除都有代价, 这取决于要添加或删除的字符值. 考虑到奶牛 ID 标签的内容以及插入或删除字母表中的每个字符的成本, 找到更改 ID 标记的最小成本, 从而满足 FJ 的需求. 一个空的 ID 标签被认为满足了读取前后相同的要求. 只有带有相关成本的字母才能添加到字符串中.
Input
来源: http://www.bubuko.com/infodetail-2653906.html