TopCoder

User's AC Ratio

77.8% (7/9)

Submission's AC Ratio

36.5% (19/52)

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

No. Testdata Range Score
1 0~4 13
2 5~9 18
3 10~17 56
4 10~19 3
5 20~25 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 500 102400 262144 1
1 500 102400 262144 1
2 500 102400 262144 1
3 500 102400 262144 1
4 500 102400 262144 1
5 500 102400 262144 2
6 500 102400 262144 2
7 500 102400 262144 2
8 500 102400 262144 2
9 500 102400 262144 2
10 500 102400 262144 3 4
11 500 102400 262144 3 4
12 500 102400 262144 3 4
13 500 102400 262144 3 4
14 500 102400 262144 3 4
15 500 102400 262144 3 4
16 500 102400 262144 3 4
17 500 102400 262144 3 4
18 500 65536 262144 4
19 500 65536 262144 4
20 1500 65536 262144 5
21 1500 65536 262144 5
22 1500 65536 262144 5
23 1500 65536 262144 5
24 1500 65536 262144 5
25 1500 65536 262144 5