b478: 有限間距最長共同子序列

DP 二維單調隊列優化

題目

solution

用deque來做單調隊列

範例測資

2 ACBDCAA ADDBCDBAC

令 sa = "ACBDCAA", sb = "ADDBCDBAC"

	A	C	B	D	C	A	A
A	1	0	0	0	0	1	1
D	0	0	0	2	0	0	0
D	0	0	0	2	0	0	0
B	0	0	2	0	0	0	0
C	0	1	0	0	3	0	0
D	0	0	0	3	0	0	0
B	0	0	2	0	0	0	0
A	1	0	0	0	0	4	4
C	0	2	0	0	4	0	0

上表為每個len[i][j]的值（sa[0～i]和sb[0～j]的GLCS）

dp式：

$if (sa[i]==sb[i])$

$len[i][j] = max(len[i-k_1][j-k_2]|k_1<=k, k_2<=k)+1$

$else$

$len[i][j] = 0$

圖一

請看圖一，要找黃色框框的值，因sa[2] == sb [3]

黃色的框框會等於紅色框框裡的最大值加1

接下來要找的是黃色框框右邊那格的值，發現要找紅色框框整個往右移的最大值

圖二

圖二想表示的是紅色框框會像這樣往右移動，所以要想一個辦法一直更新紅色框框的最大值，以求黃色框框的值

圖三

因為列一直往下跑，行也是，所以我們試著用單調隊列來維護。

每跑到一個格子，就把他加到該列的佇列中，維護其列的最大值。

有了每一列的最大值（維護後O(1)查詢），我們再用一個佇列來維護每一行的最大值。

所以我們跑回圈求出當前紅色框框的最大值，所以也可以求出黃色框框的值了囉。

找出當前紅色框框的最大值 -> 得到右下框框的值

另外，程式碼中用queue代替deque也沒有影響