stdKonjac's Blog

 要做到不可替代,就要与众不同。

【改名】

题目描述

为了跟踪所有的牛,农夫 JOHN 在农场上装了一套自动系统。他给了每一个头牛一个电子牌号,当牛走过这个系统时,牛的名字将被自动读入。每一头牛的电子名字是一个长度为 M(1<=M<=2,000)由 N(1<=N<=26) 个不同字母构成的字符串。

很快,淘气的牛找到了系统的漏洞:它们可以倒着走过读码器。一头名字为“abcba”不会导致任何问题,但是名为“abcb”的牛会变成两头牛(“abcb” 和 “bcba”)。农夫 JOHN 想改变牛的名字,使得牛的名字正读和反读都一样。例如,“abcb”可以由在尾部添加“a”。别的方法包括在头上添加“bcb”,得到“bcbabcb”或去掉“a”,得到“bcb”。JOHN 可以在任意位置添加或删除字母。因为名字是电子的,添加和删除字母都会有一定费用。添加和删除每一个字母都有一定的费用(0<=费用<=10,000)。

对于一个牛的名字和所有添加或删除字母的费用,请你找出修改名字的最小的费用。空字符串也是一个合法的名字。

输入格式

第一行:两个用空格分开的数, N 和 M 。
第二行:M 个自符,表示初始的牛的名字。
第 3…N+2 行:每行含有一个字母和两个整数,分别是添加和删除这个字母的费用。

输出格式

输出一个整数,即:改变现有名字的最小费用。

样例数据 1

输入

3 4
abcb
a 1000 1100
b 350 700
c 200 800

输出

900

要删除一个数,和要添加一个数,效果是一样的,例如abcb,添一个a和删一个a效果一样,所以当面临添加or删除时,我们选代价小的那个执行,之后就是求删数回文串问题了,dp[i][j]表示i~j的最优解,那么很明显可以划分区间,即dp[i][j]=min(dp[i][j-1]+cost[j],dp[i+1][j]+cost[i])当然算dp[i][j]得提前把dp[i][j-1]和dp[i+1][j]算出来,要注意一下循环的顺序。另外不能用memset初始化!因为比如dp[1][2]也可能由dp[2][1]转移过来!!!
下面是代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.