TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

66.7% (4/6)

Submission's AC Ratio

62.5% (15/24)

Description

又到了BONUS TIME!
這個關卡考驗的是兩個人的默契。兩個人分別會拿到長度為 $m$ 和 $n$ 的字串,皆小寫 az 組成。主持人會決定一個正整數 $k$,並請兩個人在字串中分別取出至多 $k$ 個互斥(也就是不重疊)的子字串,並且不改變次序地將些子字串照順序寫在紙上,中間用逗號隔開。獎金的的發放是這樣子決定的:如果兩個人寫在紙上的東西一模一樣,那麼他們可以拿到的錢數,等於兩人在紙上寫出的 a 的個數總和。如果有任何不一樣,則無法拿到錢。

你,身為綜藝節目的會計,想要知道這個關卡最多會發出幾塊錢。不過這兩個字串實在是太長了,因此你決定撰寫一個程式以達成目的。

(註:所謂子字串,即是取原字串中一段長度大於等於 0 的「連續」字元所形成的一個字串。例如對於 avjirye 這個字串而言,空字串、jiavjirye 都是它的子字串,而 eyravjiy 不是。)

Input Format

第一行有三個正整數 $m,n,k$,$m,n\leq 5000$代表兩個字串的長度,而 $k \leq 10$ 代表參加者所需要寫下的子字串數。
第二行和第三行分別有長度為 $m$ 和長度為 $n$ 的字串,代表兩個參加者分別會拿到的字串。

子任務(測資) 額外限制 分數
1 (0~4) $m,n\leq k+3$ 13
2 (5~9) $m,n\leq 1000$
字串只包含 'a' , 'b' 兩種字元(不含引號)
18
3 (10~17) $m,n\leq 1000$ 56
4 (10~19) $m,n\leq 1000$ 3
5 (20~25) 無限制 10

Output Format

請輸出一行,包含一個整數 $x$,代表參賽者可以拿到的獎金金額的最大值。

Sample Input

8 8 2
aabbaaaa
aaabbaab

Sample Output

8

Hints

aabbaaaa
aaabbaab
當兩個人都在紙上寫aab,aa的時候,可以獲得8元。當然,不會只有一種方法。

Problem Source

Problem set / Description by Paupière
建國中學105學年度校隊選拔:複試pD
題目改編自Codeforces

Subtasks

For Testdata: 0 ~ 4, Score: 13
For Testdata: 5 ~ 9, Score: 18
For Testdata: 10 ~ 17, Score: 56
For Testdata: 10 ~ 19, Score: 3
For Testdata: 20 ~ 25, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 500 102400
1 500 102400
2 500 102400
3 500 102400
4 500 102400
5 500 102400
6 500 102400
7 500 102400
8 500 102400
9 500 102400
10 500 102400
11 500 102400
12 500 102400
13 500 102400
14 500 102400
15 500 102400
16 500 102400
17 500 102400
18 500 65536
19 500 65536
20 1500 65536
21 1500 65536
22 1500 65536
23 1500 65536
24 1500 65536
25 1500 65536