Question

有一道编程题

Problem Description在公元3000年，人类的基因技术变得非常厉害。有个邪恶的生物学家，人类把他称为周师兄，他可以把任意的基因从细胞内移除、添加或改变，并且每个操作所花时间都为1。现在周师兄想把一个细胞M(有m个基因)变成细胞N（有n个基因），那周师兄至少要用多少时间来完成该项目。（细胞的种类和基因的顺序无关） Input输入有多组数据。
每组输入包含3行数据。第一行有两个整数，分别为m、n(1 <= m <= 30, 1 <= n <= 30)，分别代表原细胞的基因数和目标细胞的基因数。第二行有m个整数a1,a2......am(1 <= ai <= 10000000)，表示原细胞的m个基因。第三行有n个整数b1,b2......bn(1 <= bi <= 10000000)，表示目标细胞的n个基因。
当m=0，n=0 时，输入结束。 Output对于每组输入，输出一个数，表示该周师兄至少用多少时间来完成这个项目（记住换行） Sample Input3 2
1 2 3
1 2

3 3
1 2 3
1 2 4

0 0
Sample Output1
1
如果你会回答，请麻烦告诉我。谢谢啦

Answer 1

挺有趣的题目，但是也不难。
懒得写代码了，和你说下思路就好了。
首先根据题意，细胞的种类和基因的顺序无关，这句话很关键。我可以假设每个细胞的种类代表的数字是不一样的。也就是说，一个数组中不存在两个相同的值。
然后设计两个可变长度数组OLD和NEW， OLD长度为m，NEW长度为n。
从NEW[0]和OLD[0]开始进行比较，一样删除（或PASS），不一样，这里有几种情况：
1. OLD[i]中的值被删除，表现为，搜索整个NEW数组没发现OLD[i]，且NEW[i+k] == OLD[i]，则时间+k
2. OLD[i]中的值被替换了，表现为，搜索整个NEW数组没发现OLD[i]，AND 搜索整个OLD数组同样没有发现New[i]，那么同时删除这两个值，时间+1
3. New[i]中的值被添加了，表现为，与1中OLD中的值被删除了一样。

希望你能满意

Answer 2

比较水的dp