填充数字串
Problem Description
小明最近对数字很感兴趣，整天对着数字发呆，今天想到一个奇妙的问题很兴奋，但百思不得其解，现在他向你寻求帮助。
给定两个只包含数字[0..9]的数字串（不含前导0），求使用第二个数字串中的数字插入到第一个数字串中，使得插入后形成的第一个数字串中每两个相邻数字间的差值绝对值的和最大。
注意：第二个数字串中的每个数字只能使用一次；不能插入到第一个数字串的第一个位置和最后一个位置，并且第一个数字串中每两个数字间只能插入一个数字。
Input
第一行一个数字T(T<=100),表示测试数据组数。
接下来2*T行，每两行代表一组测试数据。
第一行代表第一个数字串，数字串的长度为2..1000。
第二行代表第二个数字串，数字串的长度为1..1000。
Output
对于每组测试数据，输出一行所求的最大和。
Sample Input
3
51
4
51
9
123
4
Sample Output
4
12
6
完毕。个人认为这是一道DP，但是由于数据规模有点大，我写的代码TLE了。现在还在优化我的代码。
我的思路是这样的：
1、先求得第一数字串中相邻数字间的差值绝对值，记录在origin[]中。
2、之后将第二个数字串中的第i个数字依次插入到第一个数字串的所有合法位置，求的插入后的净增长值temp[]，显然该串的长度和original[]的长度一样。求的从origin[]中每个位置到当前一步的最大值。
其中建立个标记变量mark[]，其中的值这样定义：mark[k]的值是一个二进制数对应的十进制数，每一位对应第一个数字串中的一个可插入位。mark[k]表示map[k]中各次转移在第一个数字串中的插入位置。
如果函数filledmark（ mark[k], j, total ）值为1的话，表示可以j位填充，否则表示j位已经填充过了。其中total位第一个数字串可插入位的长度。
再到使得map[k]最大的可填入temp[j]后，fillmark（ mark[k], j, total ）
3、更新map[k]
4、重复2、3，直到第二个数字串中的全部数字插入完毕。
5、遍历map[],找到最大值
发现这是一个O(T * lenb * lena ^ 2)事件复杂度的代码……囧
经过分析，时间主要是浪费在了找满足条件的j上了，我想到的一步优化是：将temp[]降序快排一下，这样在此查找满足条件的j时就会快一些，最坏的情况下，还是O(T * lenb * lena ^ 2)，幸运的话可以是O(T * lenb * lena * lg(lena))。这样就从100*1000*1000*1000降到了100*1000*1000*3。
可能分析的不对，还望高手请教。
代码见我的CSDN博客 http://blog.csdn.net/clhmw/archive/2010/05/17/5602110.aspx