1427 . Bonus time
TopCoder
Tags
Description
又到了BONUS TIME！
這個關卡考驗的是兩個人的默契。兩個人分別會拿到長度為 $m$ 和 $n$ 的字串，皆小寫 a 到 z 組成。主持人會決定一個正整數 $k$，並請兩個人在字串中分別取出至多 $k$ 個互斥（也就是不重疊）的子字串，並且不改變次序地將些子字串照順序寫在紙上，中間用逗號隔開。獎金的的發放是這樣子決定的：如果兩個人寫在紙上的東西一模一樣，那麼他們可以拿到的錢數，等於兩人在紙上寫出的 a 的個數總和。如果有任何不一樣，則無法拿到錢。
你，身為綜藝節目的會計，想要知道這個關卡最多會發出幾塊錢。不過這兩個字串實在是太長了，因此你決定撰寫一個程式以達成目的。
（註：所謂子字串，即是取原字串中一段長度大於等於 0 的「連續」字元所形成的一個字串。例如對於 avjirye 這個字串而言，空字串、ji、avjirye 都是它的子字串，而 eyr、avjiy 不是。）
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 1
8 8 2
aabbaaaa
aaabbaab
aabbaaaa
aaabbaab
Sample Output 1
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 |