2020-2021:teams:manespace:最长上升子序列
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:最长上升子序列 [2020/06/01 12:06] 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$ 的最长公共子序列 | + | 顾名思义，将数组 $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] =$ |
| 0 ;(i == 0 || j == 0) | 0 ;(i == 0 || j == 0) | ||
| dp[i-1][j-1] + 1 ;(a[i] == b[j]) | dp[i-1][j-1] + 1 ;(a[i] == b[j]) | ||
| max{dp[i][j-1], dp[i-1][j]} ;(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> | <code> | ||
| - | for(int i = 1; i <= n; i++){ | + | for(int i = 1; i <= n; ++i){ |
| - | for(int j = 1; j <= m; j++){ | + | for(int j = 1; j <= m; ++j){ |
| - | if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1] + 1; | + | if(a[i] == b[j]){ |
| - | else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); | + | 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> | </code> | ||
| + | 答案即为 $dp[n][m]$ | ||
| ==== Solution 4 : 据说可以用树状数组？ ==== | ==== Solution 4 : 据说可以用树状数组？ ==== | ||
| - | <del>吓得我赶紧去学</del> 先前的[[树状数组]]有待完善... | + | 树状数组可参考本队上一专题→[[树状数组]] |
| + | |||
| + | <del>但是到考期了你懂的</del> | ||
| + | |||
| + | 这里不讲了，也是 $O(nlogn)$ 的复杂度，有需要自行查找吧 | ||
2020-2021/teams/manespace/最长上升子序列.1590984416.txt.gz · 最后更改: 2020/06/01 12:06 由 intouchables
