{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e跟踪所有奶牛可能是一项棘手的任务,所以农夫约翰安装了一个系统来自动化这个过程。他在每头奶牛身上安装了一个电子ID标签,系统会在奶牛经过扫描仪时读取它们。每个ID标签的内容目前是一个长度为 \u003ci\u003eM\u003c/i\u003e(1 ≤ \u003ci\u003eM\u003c/i\u003e ≤ 2,000)的字符串,由 \u003ci\u003eN\u003c/i\u003e(1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 26)个不同符号(即小写罗马字母表)组成。\u003c/p\u003e\u003cp\u003e奶牛是调皮的生物,有时会试图欺骗系统,倒着走。虽然一个ID为 \"abcba\" 的奶牛无论向哪个方向走都会读取相同的内容,但一个ID为 \"abcb\" 的奶牛可能会注册为两个不同的ID(\"abcb\" 和 \"bcba\")。\u003c/p\u003e\u003cp\u003e约翰希望更改奶牛的ID标签,使其无论奶牛向哪个方向走都能读取相同的内容。例如,\"abcb\" 可以通过在末尾添加 \"a\" 来变为 \"abcba\",使得ID是回文的(正向和反向读取内容相同)。将ID更改为回文的其他方法包括在开头添加三个字母 \"bcb\" 以得到ID \"bcbabcb\",或者删除字母 \"a\" 以得到ID \"bcb\"。可以在字符串的任何位置添加或删除字符,得到比原始字符串长或短的字符串。\u003c/p\u003e\u003cp\u003e不幸的是,由于ID标签是电子的,每个字符的插入或删除都有一个成本(0 ≤ \u003ci\u003ecost\u003c/i\u003e ≤ 10,000),具体取决于要添加或删除的字符值。给定奶牛的ID标签内容和插入或删除每个字母的成本,找出更改ID标签以满足约翰要求的最小成本。将空ID标签视为满足正向和反向读取相同内容的要求。只能添加带有关联成本的字母到字符串中。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"Line 1: 两个用空格分隔的整数: \u003ci\u003eN\u003c/i\u003e 和 \u003ci\u003eM\u003c/i\u003e\r\u003cbr\u003eLine 2: 此行包含恰好 \u003ci\u003eM\u003c/i\u003e 个字符,构成初始ID字符串\r\u003cbr\u003eLines 3..\u003ci\u003eN\u003c/i\u003e+2: 每行包含三个用空格分隔的实体: 输入字母表中的一个字符和两个整数,分别是添加和删除该字符的成本。"}},{"title":"输出","value":{"format":"HTML","content":"Line 1: 一行,一个整数,表示更改给定名称标签的最小成本。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 4\r\nabcb\r\na 1000 1100\r\nb 350 700\r\nc 200 800\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e900\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"如果我们在末尾插入一个 \"a\" 得到 \"abcba\",成本将为 1000。如果我们删除开头的 \"a\" 得到 \"bcb\",成本将为 1100。如果我们在字符串开头插入 \"bcb\",成本将为 350 + 200 + 350 \u003d 900,这是最小成本。"}}]}