TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  課程の中心  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3640
  • 問題
  • P3640数列
    制限 : 時間制限 : 10000 MS   メモリ制限 : 65536 KB
    問題説明

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

    入力形式

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

    出力形式

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

    サンプル入力 1

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

    サンプル出力 1

    4

    サンプル入力 2

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

    サンプル出力 2

    6

    サンプル入力 3

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

    サンプル出力 3

    5

    ヒント

    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