TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Course  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3640
  • Problem
  • P3640数列
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    有X,Y两个整数数列,现在需要我们用最小的操作次数,将X数列转换成与Y相同的数列。
    对于X数列,我们有以下三种操作:
    1.删除一个数字;
    2.插入一个数字;
    3.将一个数字改为另一个数字;
    请你计算出完成转换所需的最小操作数。

    Input Format

    第一行,两个整数n和m,分别代表X,Y两个数列的长度。
    第二行,n个空格间隔的整数,表示X数列
    第三行,m个空格间隔的整数,表示Y数列

    Output Format

    一行,一个整数,表示最少所需的操作数。

    Sample Input 1

    7 5
    1 2 3 4 5 6 7
    8 2 3 8 7

    Sample Output 1

    4

    Sample Input 2

    8 7
    1 8 2 7 6 1 2 6 
    2 1 7 8 7 6 8 

    Sample Output 2

    6

    Sample Input 3

    10 8
    1 1 3 3 1 2 2 2 1 1 
    1 1 3 3 2 1 3 3 

    Sample Output 3

    5

    Hint

    1<=n,m<=2000, 0<=数列中的数字<=1000

    样例1说明:
    第一步:将数字1修改为8
    8 2 3 4 5 6 7
    8 2 3 8 7
    第二步:将数字4删掉
    8 2 3 5 6 7
    8 2 3 8 7
    第三步:将数字5删掉
    8 2 3 6 7
    8 2 3 8 7
    第四部:将数字6修改为8
    8 2 3 8 7
    8 2 3 8 7