2020-2021:teams:manespace:最长上升子序列
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:最长上升子序列 [2020/06/01 12:18] intouchables [Solution 3 : 转LCS] |
2020-2021:teams:manespace:最长上升子序列 [2020/06/04 15:53] (当前版本) intouchables [Solution 4 : 据说可以用树状数组？] |
||
|---|---|---|---|
| 行 78: | 行 78: | ||
| ==== Solution 3 : 转LCS ==== | ==== Solution 3 : 转LCS ==== | ||
| - | 顾名思义，将数组 $a$ 排序得到新数组 $b$，问题转化为求 $a,b$ 的最长公共子序列，长度分别为 $n,m$ | + | 顾名思义，将数组 $a$ 排序得到新数组 $b$，问题转化为求 $a,b$ 的**最长公共子序列**，长度分别为 $n,m$ |
| 此处只给出其 $DP$ 状态转移方程，以 $dp[i][j]$ 表示 $a[i]$ 和 $b[j]$ 的LCS长度，状态转移方程 $dp[i][j] =$ | 此处只给出其 $DP$ 状态转移方程，以 $dp[i][j]$ 表示 $a[i]$ 和 $b[j]$ 的LCS长度，状态转移方程 $dp[i][j] =$ | ||
| 行 88: | 行 88: | ||
| 解的追踪（不予详解）：设一标记数组 $tr[n][m]$ ，标记依据 $dp$ 方程设立，最后从 $tr[n][m]$ 回溯寻找 $a[i] == b[j]$的标记，压栈即可 | 解的追踪（不予详解）：设一标记数组 $tr[n][m]$ ，标记依据 $dp$ 方程设立，最后从 $tr[n][m]$ 回溯寻找 $a[i] == b[j]$的标记，压栈即可 | ||
| - | 代码 | + | 伪码 |
| <code> | <code> | ||
| for(int i = 1; i <= n; ++i){ | for(int i = 1; i <= n; ++i){ | ||
| 行 122: | 行 122: | ||
| ==== Solution 4 : 据说可以用树状数组？ ==== | ==== Solution 4 : 据说可以用树状数组？ ==== | ||
| - | <del>吓得我赶紧去学</del> 先前的[[树状数组]]有待完善... | + | 树状数组可参考本队上一专题→[[树状数组]] |
| + | |||
| + | <del>但是到考期了你懂的</del> | ||
| + | |||
| + | 这里不讲了，也是 $O(nlogn)$ 的复杂度，有需要自行查找吧 | ||
2020-2021/teams/manespace/最长上升子序列.1590985110.txt.gz · 最后更改: 2020/06/01 12:18 由 intouchables
