2020-2021:teams:manespace:最长上升子序列

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:manespace:最长上升子序列 [2020/05/30 00:32]
iuiou
+++ 2020-2021:teams:manespace:最长上升子序列 [2020/06/04 15:53] (当前版本)
intouchables [Solution 4 : 据说可以用树状数组？]
@@ 行 75: / 行 75: @@
 最终 $f[cnt]$ 即为答案
-==== Solution 3 : 据说可以用树状数组？ ====
-<del>吓得我赶紧去学</del>  先前的[[树状数组]]有待完善...
+==== Solution 3 : 转LCS ====
+顾名思义，将数组 $a$ 排序得到新数组 $b$，问题转化为求 $a,b$ 的**最长公共子序列**，长度分别为 $n,m$
+此处只给出其 $DP$ 状态转移方程，以 $dp[i][j]$ 表示 $a[i]$ 和 $b[j]$ 的LCS长度，状态转移方程 $dp[i][j] =$
+;(i == 0 || j == 0)
+  dp[i-1][j-1] + 1 ;(a[i] == b[j])
+  max{dp[i][j-1], dp[i-1][j]} ;(a[i] != b[j])
+解的追踪（不予详解）：设一标记数组 $tr[n][m]$ ，标记依据 $dp$ 方程设立，最后从 $tr[n][m]$ 回溯寻找 $a[i] == b[j]$的标记，压栈即可
+伪码
+<code>
+for(int i = 1; i <= n; ++i){
+	for(int j = 1; j <= m; ++j){
+		if(a[i] == b[j]){
+			dp[i][j] = dp[i-1][j-1] + 1;
+			tr[i][j] = 3;
+		}
+		else{
+			dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
+			tr[i][j] = dp[i-1][j] > dp[i][j-1] ? 1 : 2;
+		}
+	}
+}。
+int x = n, y = m, t;
+int dx[4] = {INF, -1, 0, -1};
+int dy[4] = {INF, 0, -1, -1};
+stack <int>z;
+while(tr[x][y]){
+	if(tr[x][y] == 3) z.push(a[x]);
+	t = tr[x][y];
+	x += dx[t];
+	y += dy[t];
+}
+while(!z.empty()){
+	printf("%d ", z.top());
+	z.pop();
+}
+</code>
+答案即为 $dp[n][m]$
+==== Solution 4 : 据说可以用树状数组？ ====
+树状数组可参考本队上一专题→[[树状数组]]
+<del>但是到考期了你懂的</del>
+这里不讲了，也是 $O(nlogn)$ 的复杂度，有需要自行查找吧

2020-2021/teams/manespace/最长上升子序列.1590769942.txt.gz · 最后更改: 2020/05/30 00:32 由 iuiou