给出两个字串A，B。将A字串转化为B字串，转化一共有两种方式:删除连续的n个字符，一次操作费用为2。增加连续的n个字符(增加的字符是什么由你决定)，一次操作费用为n+2。求把A变为B最小费用。
输入:
第一行输入一个正整数T(1 <= T <= 10)，表示有T组测试数据。
对于每组测试数据，有两行字符串A, B（字符串长度不超过2000，字符仅包含小写字母）。
输出:
对于每组测试数据，输出一行一个整数，表示最小费用。
样例输入:
2
dsafsadfadf
fdfd
aaaaaaaa
bbbbbbbb
样例输出:
7
12
答案提示:
“dsafsadfadf” 变成 “fdfd” 最少的代价的一种方法是：
（1）“dsafsadfadf” -> “f” 删除连续的10个，代价2 ；
（2）“f” -> “fdfd” 增加连续的3个（”dfd”），代价为3 ＋ 2 ＝ 5
���共的最小代价为2 ＋ 5 ＝ 7，其他方法的代价都不小于7 。
“aaaaaaaa” 变成 “bbbbbbbb” 最小代价的一种方法是：
（1）“aaaaaaaa” 全部删除，代价2；
（2）增加8个连续的’b’，代价10 。
总共的最小代价为2 ＋ 10 ＝ 12 。
注意，有些最优的方案可能要做多次的删除和增加操作，不限于两次。
问题分析：
从给定的问题描述，我们可以得到如下几条信息：
（1）A串变为B串，只有两种变换的方式，一是删除，二是增加。增加和删除的位置可以在A串中的任意位置；
（2）每一次删除和增加都需要额外的代价，因此，对同一段字符，应该使用贪心思想，尽可能的连续删除和连续增加；
（3）A串和B串的相同的首尾子串是不需要考虑的。
除去相同的首尾子串，得到的子串A’和B’，将A’变为B’时，因为此时的A’的首尾字符与B’的首尾字符是不相同的，所以，对A’此时的操作有两种：
（1）对A’从左起和右起使用贪心的思想删除连续的字符；
（2）对A’从左起和右起用贪心的思想分别增加B’的左起连续的字符和B’的右起连续的字符。
这里为什么不考虑从A的中间部分开始插入和删除，是因为这样做的话，A’的首尾位字符与B’的首尾字符还是不相同，还是需要进行删除或者增加的操作，很明显这样不是最优的，所以抛弃这种做法。
具体实现请，参考如下代码：
/******************************************* *@brief:将字符串a变为字符串b的最小费用 *@param:a:字符串a;b:字符串b;i:a的起始下标;ir:a的结束下标;j:b的起始下标;jr:b的结束下标 *******************************************/ int func1 (const char a[] ,const char b[] ,int i ,int ir ,int j ,int jr) { //ab有相同前缀，则去除掉也不影响 while (i <= ir && j <= jr && a[i] == b[j]) { i++ ; j++ ; } //ab有相同后缀，则去除掉也不影响 while (i <= ir && j <= jr && a[ir] == b[jr]) { ir-- ; jr-- ; } if (i > ir) { //如果a是空串，则只需增加操作，代价是b的长度+2 return (jr + 1 - j) + 2 ; } else if (j > jr) { //如果b是空串，则只需删除操作，代价是2 return 2 ; } //如果ab无公共前后缀，则代价是求a的所有前后子串转为b的最小值 //最坏的情况是将a全部删除再增加到b int tmp = 2 + (jr + 1 - j) + 2 ; //a的非空后子串 for (int k = i + 1 ; k <= ir ; k++) tmp = min (tmp ,2 + func1 (a ,b ,k ,ir ,j ,jr)) ; //a的非空前子串 for (int k = ir - 1 ; k >= i ; k--) tmp = min (tmp ,2 + func1 (a ,b ,i ,k ,j ,jr)) ; //在a的左边增加连续的b的非空前子串 for (int k = j + 1 ; k <= jr ; k++) tmp = min (tmp ,(k - j) + 2 + func1 (a ,b ,i ,ir ,k ,jr)) ; //在a的右边增加连续的b的非空后子串 for (int k = jr - 1 ; k >= j ; k--) tmp = min (tmp ,(jr - k) + 2 + func1 (a ,b ,i ,ir ,j ,k)) ; return tmp ; }