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 : 据说可以用树状数组？] |
||
|---|---|---|---|
| 行 17: | 行 17: | ||
| 为保证升序，状态转移需从 $a[i]$ **之前** 比 $a[i]$ **小** 的元素转移而来。<del>你说，是不是啊</del> | 为保证升序，状态转移需从 $a[i]$ **之前** 比 $a[i]$ **小** 的元素转移而来。<del>你说，是不是啊</del> | ||
| - | 则状态转移方程 $dp[i] = max(dp[i], dp[j] + 1)$ ，其中 $j < i a[j] < a[i]$， 复杂度$O(n^2)$。<del>你说，是不是啊*2</del> | + | 则状态转移方程 $dp[i] = max(dp[i], dp[j] + 1)$ ，其中 $(j < i) a[j] < a[i]$， 复杂度$O(n^2)$。<del>你说，是不是啊*2</del> |
| 如需输出任意一解，可设置一追踪标记 $tr$，与 $ans$ 同步更新为当前位置 $i$ | 如需输出任意一解，可设置一追踪标记 $tr$，与 $ans$ 同步更新为当前位置 $i$ | ||
| 行 75: | 行 75: | ||
| 最终 $f[cnt]$ 即为答案 | 最终 $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] =$ | ||
| + | |||
| + | 0 ;(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/最长上升子序列.1590769920.txt.gz · 最后更改: 2020/05/30 00:32 由 iuiou
