2040 . 片段刪除
TopCoder
Description
輸入兩個字串，請運用片段刪除的方式，讓這兩個字串變成一樣，規則如下。每次可從輸入的字串中選取一個長度不超過$L$ 的連續片段刪除，請問能否在$K$ 次內，完成這項任務。若是可以，請輸出最少刪除的次數，否則輸出Impossible。
例如$L=3,K=2$，輸入的兩個字串分別為abcdcbaa 與aaa，則abcdcbaa-->abbaa-->aaa，其中紅色區塊是欲刪除的字串，所以2 次內可以完成任務，且2 是最少的操作次數。又如輸入的字串為abaaabe 與accaaae，$L=2,K=3$，則abaaabe-->aaaabe-->aaaae，且accaaae-->aaaae，因此3 次內可以完成任務。
Input Format
每筆測資共有3 列，第1 列為第1 個輸入字串，第2 列為第2 個輸入字串，輸入字串皆由小寫英文字母組成；第3 列共有兩個正整數，分別為$L$ 與$K$，兩者均可存入32 位元整數。
Output Format
針對每筆測資，輸出滿足題意之最少刪除次數，或是Impossible。
Sample Input 1
aaaaa
aaaaaaa
1 2
aaaaaaa
1 2
Sample Output 1
2
Sample Input 2
ababababab
bababababa
2 2
bababababa
2 2
Sample Output 2
2
Sample Input 3
aaaaaaaaaaaaa
bbbbbbbbbbbbb
2 2
bbbbbbbbbbbbb
2 2
Sample Output 3
Impossible
Hints
本題共有3 個子題，每一子題有多筆測資：
第1 子題有5 筆測資，兩個輸入字串中僅有字母a，長度均小於130，全解出可得11 分；
第2 子題有5 筆測資，兩個輸入字串長度均小於100，且$L=1$，全解出可得22 分；
第3 子題有7 筆測資，兩個輸入字串長度均小於10000 個字元；$L \leq 100$ 且$K \leq 10$。全解出可得67 分。
Problem Source
106學年度高級中學資訊學科能力競賽決賽 程式設計試題第七題
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 11 |
| 2 | 5~9 | 22 |
| 3 | 10~16 | 67 |