{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cp\u003e一句话题意:每个字母添加和删除都相应代价(可以任意位置 增加/删除),求把原串变成回文串的最小代价\n \u003cp\u003e\u003cp\u003e\u003cp\u003e保持对所有奶牛的跟踪是一项棘手的任务,因此农场主约翰已经安装了一个系统来实现自动化。他在每头奶牛身上安装了一个电子ID标签,系统将在奶牛经过扫描仪时读取。每个ID标记是从字母表中提取的一个字符串。\u003c/p\u003e\n \u003cp\u003e奶牛,它们是淘气的动物,有时试图通过倒着走来欺骗系统。如果一头奶牛的ID是“abcba”,那么无论她怎么走,它都能读到同样的东西,而拥有“abcb”的奶牛可能会注册为两个不同的ID(“abcb”和“bcba”)。\u003c/p\u003e\n \u003cp\u003eFJ希望改变奶牛的ID标签,这样无论奶牛走过哪个方向,他们都能读到同样的标签。例如,“abcb”可以通过在末尾添加“a”来改变,从而形成“abcba”,这样ID就会是一个回文串。更改ID的其他一些方法包括将三个字母“bcb”添加到“abcb”的开始,以获得ID“bcbabcb”或删除字母“a”以产生ID“bcb”。我们可以在字符串中的任意位置添加或删除字符,其长度比原来的字符串长或短。\u003c/p\u003e\n \u003cp\u003e不幸的是,ID标签是电子信息,每个字符插入或删除都有代价,这取决于要添加或删除的字符值。考虑到奶牛ID标签的内容以及插入或删除字母表中的每个字符的成本,找到更改ID标记的最小成本,从而满足FJ的需求。一个空的ID标签被认为满足了读取前后相同的要求。只有带有相关成本的字母才能添加到字符串中。\u003c/p\u003e\n \u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n Line 1: 两个空间分隔的整数:N和M (1 ≤ M ≤ 2,000) (1 ≤ N ≤ 26)\n \u003cbr\u003eLine 2: 这一行包含了组成初始ID字符串的M个字符\n \u003cbr\u003eLines 3..\n \u003ci\u003eN\u003c/i\u003e+2: 每行包含三个空间分隔的实体:输入字母和两个整数的字符,分别是添加和删除该字符的成本(Ci\u003c\u003d10000)。\n \u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n Line 1: 单个整数的一行,这是更改给定名称标签的最小代价。\n\n \u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e3 4\nabcb\na 1000 1100\nb 350 700\nc 200 800\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e900\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 如果我们在最后插入一个“a”,得到“abcba”,成本是1000。如果我们在开始的时候删除“a”,就会得到“bcb”,代价就是1100。如果我们在字符串的开始处插入“bcb”,代价将是350 + 200 + 350 \u003d 900,这是最小值。\n \u003c/div\u003e"}}]}