\(
\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"}}
\)
助教判斷抄襲的方法
題目敘述
ㄠㄨ
各位應該知道吧,助教在一開始的時候就有說會判斷抄襲了,當然助教判斷抄襲的方法是非常困難的,不過這裡提供一個簡單的版本希望大家能實做出來。
對於字串$A$和$B$,我們目標是要把$A$進行一些修改讓他變成$B$,這些修改定義如下:
- 在$A$的任意位置插入一個字符,花費是$c0$
- 刪除$A$的任意位置的一個字符,花費是$c1$
- 把$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