本題記憶體限制 16MB
子序列的意思是對於原序列移除掉一些字元,但是不改變字元的順序的序列。
EX:
$ADE$ 與 $BD$ 為 $ABCDE$ 的其中兩個子序列。
然而 $DEA$ 不是 $ABCDE$ 的子序列。
你現在有 $2$ 個長度為 $N$ 的序列 $S_1, S_2$ ,其中只有包括大寫字母。
你現在想要找一個最長共同序列 $s_{com}$
共同子序列 $s_{com}$ 的特色就是屬於序列 $S_1, S_2$ 的子序列。
EX:
$S_1=ABCDD$
$S_2=ABDDE$
那麼序列 $DD$ 是其中一個共同子序列。
而序列 $ABDD$ 是其中一個最長共同子序列。
第一行有一個整數 $N$($1 \leq N \leq 3000$)
接下來有 $2$ 行,每一行有一個序列,長度為 $N$,序列為大寫字母組成。
輸出一個整數,代表這個最長的共同子序列的長度。
LCS小知識!
記得LCS並不是唯一解喔!
From 演算法筆記
No. | Testdata Range | Score |
---|---|---|
1 | 0~7 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 3000 | 16384 | 65536 | |
1 | 3000 | 16384 | 65536 | |
2 | 3000 | 16384 | 65536 | |
3 | 3000 | 16384 | 65536 | |
4 | 3000 | 16384 | 65536 | |
5 | 3000 | 16384 | 65536 | |
6 | 3000 | 16384 | 65536 | |
7 | 3000 | 16384 | 65536 |