配飾_ssl2569_LCIS

Description

但是小L想考驗一下小T,是以,他給小T出了一個難題.

他拿出了他所有的配飾并擺成兩列,如果兩個配飾的型号一樣并且出現在不同列中,那麼我們就可以認為這兩個配飾為情侶配飾.另外，由于某些不為人知的原因，我們規定,在順序選取的情況下,每標明的一對配飾必須比前面標明的一對配飾的型号要大.小T最多能夠選取多少對配飾呢?

Input

共四行

第一行一個數N 表示第一列配飾的個數

第二行N個數 分别表示第一列配飾的型号

第三行一個數M 表示第二列配飾的個數

第四行M個數 分别表示第二列配飾的型号

Output

僅一個數K,表示最多能選取的情侶配飾的對數.

資料範圍：

30%的資料 n,m<=10

70%的資料 n,m<=100

100%的資料 n,m<=5000

Analysis

裸的LCIS然而錯了于是學習一下

類似之前的想法 f[i][j] 表示a數組前 i 項比對到b數組j 項的LCIS，那麼不難得出

若 a[i]≠b[j] 則 f[i][j]=f[i−1][j]

這一項不比對，那麼狀态為前一項的LCIS

若 a[i]=b[j] 則

f[i][j]=max{f[i−1][k]}+1　　1≤k≤j−1

這一項比對，那麼狀态可以在之前的基礎上增加長度

然後k可以優化，數組可以滾，大概就是這樣

Code