35. 助教判斷抄襲的方法

0 Judge

Code: 0


\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

助教判斷抄襲的方法

題目敘述

sprout
ㄠㄨ

各位應該知道吧,助教在一開始的時候就有說會判斷抄襲了,當然助教判斷抄襲的方法是非常困難的,不過這裡提供一個簡單的版本希望大家能實做出來。

對於字串$A$和$B$,我們目標是要把$A$進行一些修改讓他變成$B$,這些修改定義如下:
  1. 在$A$的任意位置插入一個字符,花費是$c0$
  2. 刪除$A$的任意位置的一個字符,花費是$c1$
  3. 把$A$的任意位置的一個字符修改成另一字符,花費是$c2$

例如$A="abcde"$,$B="abdefg"$,則$B$可以由$A$刪除字符$'c'$後,再插入字符$'f','g'$到正確的位置這三次轉換變成,總花費為$c1+2*c0$。現在給你$c0,c1,c2$和$A,B$,請你輸出把$A$轉換到$B$所需要的最小總花費。

輸入說明

第一行有三個正整數$c0,c1,c2$,皆大於0且小於等於1000000,接著有多行,不會超過20行,以EOF結尾,每行有兩個字串$A,B$,由小寫字母組成。

輸出說明

對於每組$A,B$,輸出$A$變到$B$的最小花費

範例輸入 1

1 1 1
abcde abdefg
aassjdfghdgdf hlknakjnakjs

範例輸出 1

3
13

範例輸入 2

1 1000 1
abcde abdefg
aassjdfghdgdf hlknakjnakjs

範例輸出 2

4
1012

配分方法

  • 0% 範例測資
  • 40% $|A|,|B| \leq 100$
  • 60% $|A|,|B| \leq 1000$

Hints

DP

備註

DP

Judge Setting

run-time limit: 170 ms
memory limit: 49637376 byte
測資數量: 0