0 Judge
Code: 0
有兩個陣列$a[1]\cdots a[N]$和$b[1]\cdots b[M]$，從兩個陣列中各選一個子序列，它們要長得完全一樣，而且除了第一項之外每一項都必須大於前一項。子序列的長度最大可以是多少？
第一行有兩個正整數$N$和$M$。($1\leq N, M \leq 2000$)
第二行有$N$個正整數$a[1]\cdots a[N]$。($1\leq a[i] \leq 10^9$)
第三行有$M$個正整數$b[1]\cdots b[M]$。($1\leq b[i] \leq 10^9$)
最長共同遞增子序列的長度。
子任務一(50%)：$1\leq N, M \leq 300$
子任務二(50%)：無特別限制
4 7
3 1 3 4
4 2 3 4 3 1 42LCIS是$[1,4]$或$[3,4]$。
因為這題要從頭開始解出來真的有點困難，所以我決定在這裡給一些提示：
$d[i][j]$=$a[i]$不一定要選，$b[j]$一定要選的LCIS長度。分兩種情況討論：
$a[i]\neq b[j]$，那麼因為$b[j]$一定要選，所以$a[i]$一定不選，等於忽略$a[i]$的LCIS長度，$d[i][j]=d[i-1][j]$。
$a[i] = b[j]$，那麼因為$b[j]$一定要選，所以$a[i]$也一定可以選。此時LCIS的最後一項是$a[i]$(也是$b[j]$)，那麼枚舉LCIS的前一項$b[l]$，相對應的狀態是$d[i-1][l]$，可以得到轉移式$d[i][j]=max(d[i-1][l]|0\leq l < j, b[l]<b[j]) + 1$。$l=0$代表自己成為一個長度$1$的LCIS。
這樣就有了$O(NM^2)$的解法，可以拿到$50$分。
能不能進一步直接知道要選哪一個$l$呢？需要利用一些前綴最大值的技巧來優化上面的轉移式。就提示到這裡:)