249 . 天王寺璃奈與她的璃奈板
TopCoder
Tags
Description
我...我是璃奈，是個非常可愛的女孩，可是我不擅長把感情表現在臉上，因此總是被覺得是個冷淡的女孩子(;﹏;)，於是我想到了一個很棒的方法可以向大家傳達我的感情，我決定製作一個秘密道具名為「小璃奈板」。讓我可以在上面畫上表情來傳達我的感受。
但是但是...若是要在演唱會上使用璃奈板的話有點麻煩，我沒辦法快速的變換我的表情，這樣觀眾會不會感受不到我的心情呢？我的心情永遠是跟大家再一起的呦！我希望能把最歡樂的那面傳遞給你！
所...所以你願意幫我的忙嗎？(๑• . •๑)
我可以給你兩組我的表情順序 $E_1, E_2$，你可以把花費 $0$ 元其中的一些表情刪掉，或是跟我說你希望在第任一一個表情之間花費 $c_k$ 元插入我的第 $k$ 種表情，不知道你可以不可以在經費 $W$ 元之內幫我把我的兩組表情順序變成一樣呢？我希望留下來的表情順序越長越好呦ξ( ✿＞◡❛)
接下來跟著我一起喊『天使，天才，天王寺』！這樣一點也不奇怪，對吧？
Input Format
第一行有三個正整數 $N, M, W$ 代表表情順序的長度以及璃奈給你的經費。
接下來的兩行分別有兩個僅由小寫英文字母組成的字串 $E_1, E_2$ 代表璃奈的表情順序。
最後一行有 26 個正整數 $c_k$ 分別代表加入第 $k$ 個英文字母所代表的表情所需要的金錢。
- $N, M\leq 300$
- $W \leq 10^ 9$
- $|E_1|=N, |E_2| = M$
- $c_k \leq 10^ 9$
Output Format
輸出一個數字代表你修改過後的璃奈表情順序最多可以多長。
Sample Input 1
abc
abd
1 1 3 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Sample Output 1
Sample Input 2
ioicamp
acmicpccamp
100 200 300 400 500 600 700 800 30 1000 1100 1200 1300 1400 30 1600 1700 1800 1900 2000 2100 2200 2300 2400 2500 2600
Sample Output 2
Hints
對於第一組範例測資，一種可能的最佳修改方式是讓兩個表情序列都變成 abaa，這樣需要花費 $(1+1) + (1+1)=4$ 元
abc $\rightarrow$ ab $\rightarrow$ aba $\rightarrow$ abaa
abd $\rightarrow$ ab $\rightarrow$ aba $\rightarrow$ abaa
對於第二組範例測資，一種可能的最佳修改方式是讓兩個表情序列都變成 ioicamp，這樣 $40+20 = 60$ 元
acmicpccamp $\rightarrow$ icamp $\rightarrow$ oicamp $\rightarrow$ ioicamp
Problem Source
IOICamp 2020 Day3 pD
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~19 | 無額外限制 | 100 |