249 . 天王寺璃奈與她的璃奈板

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Fysty

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

57.1% (4/7)

Tags

ioicamp ioicamp-2020

Description

我...我是璃奈，是個非常可愛的女孩，可是我不擅長把感情表現在臉上，因此總是被覺得是個冷淡的女孩子(;﹏;)，於是我想到了一個很棒的方法可以向大家傳達我的感情，我決定製作一個秘密道具名為「小璃奈板」。讓我可以在上面畫上表情來傳達我的感受。

但是但是...若是要在演唱會上使用璃奈板的話有點麻煩，我沒辦法快速的變換我的表情，這樣觀眾會不會感受不到我的心情呢？我的心情永遠是跟大家再一起的呦！我希望能把最歡樂的那面傳遞給你！

所...所以你願意幫我的忙嗎？(๑• . •๑)

我可以給你兩組我的表情順序 E1,E2，你可以把花費 0 元其中的一些表情刪掉，或是跟我說你希望在第任一一個表情之間花費 ck 元插入我的第 k 種表情，不知道你可以不可以在經費 W 元之內幫我把我的兩組表情順序變成一樣呢？我希望留下來的表情順序越長越好呦ξ( ✿＞◡❛)

接下來跟著我一起喊『天使，天才，天王寺』！這樣一點也不奇怪，對吧？

Input Format

第一行有三個正整數 N,M,W 代表表情順序的長度以及璃奈給你的經費。

接下來的兩行分別有兩個僅由小寫英文字母組成的字串 E1,E2 代表璃奈的表情順序。

最後一行有 26 個正整數 ck 分別代表加入第 k 個英文字母所代表的表情所需要的金錢。

  • N,M≤300
  • W≤109
  • |E1|=N,|E2|=M
  • ck≤109

Output Format

輸出一個數字代表你修改過後的璃奈表情順序最多可以多長。

Sample Input 1

3 3 5
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

4

Sample Input 2

7 11 60
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

7

Hints

對於第一組範例測資，一種可能的最佳修改方式是讓兩個表情序列都變成 abaa，這樣需要花費 (1+1)+(1+1)=4 元

abc → ab → aba → abaa

abd → ab → aba → abaa

對於第二組範例測資，一種可能的最佳修改方式是讓兩個表情序列都變成 ioicamp，這樣 40+20=60 元

acmicpccamp → icamp → oicamp → ioicamp

Problem Source

IOICamp 2020 Day3 pD

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~19 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2500 524288 65536 1 2
1 2500 524288 65536 1 2
2 2500 524288 65536 2
3 2500 524288 65536 2
4 2500 524288 65536 2
5 2500 524288 65536 2
6 2500 524288 65536 2
7 2500 524288 65536 2
8 2500 524288 65536 2
9 2500 524288 65536 2
10 2500 524288 65536 2
11 2500 524288 65536 2
12 2500 524288 65536 2
13 2500 524288 65536 2
14 2500 524288 65536 2
15 2500 524288 65536 2
16 2500 524288 65536 2
17 2500 524288 65536 2
18 2500 524288 65536 2
19 2500 524288 65536 2
Submit
Back to Top