Server Time:

User's AC Ratio in this contest

51.1% (23/45)

Submission's AC Ratio in this contest

13.5% (26/192)

Description

本題記憶體限制 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$ 是其中一個最長共同子序列。

Input Format

第一行有一個整數 $N$($1 \leq N \leq 3000$)
接下來有 $2$ 行,每一行有一個序列,長度為 $N$,序列為大寫字母組成。

Output Format

輸出一個整數,代表這個最長的共同子序列的長度。

Sample Input 1

5
ABCDD
ABDDE

Sample Output 1

4

Hints

LCS小知識!
記得LCS並不是唯一解喔!

From 演算法筆記

此題延伸:https://judge.csie.ncku.edu.tw/problems/107

Problem Source

Subtasks

No. Testdata Range Score
1 0~7 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 16384 65536 1
1 3000 16384 65536 1
2 3000 16384 65536 1
3 3000 16384 65536 1
4 3000 16384 65536 1
5 3000 16384 65536 1
6 3000 16384 65536 1
7 3000 16384 65536 1