HDU4991权值线段树优化DP
题目
一个长度为$n(n<=10000)$的数组,问长度为$m(m<=100)$的上升子序列数量。
解题思路
离散化后,最多10000个数
暴力转移
1 | // 令DP[i][j]为以i结尾长度为j的上升子序列方案数 |
复杂度为$O(n^2m)$。
权值线段树优化
想办法优化,线段树可以将一个$n$优化到$log(n)$
1 | struct node |
线段树最底层的 $tr[i].len[j]$表示以$i$为最后一个数,长度为$j$的上升子序列数量。
当要插入数$x$时,我们将区间$[1,x-1]$的所有数的$len[i]$加起来,得到$prefix.len[i-1]$,以$x$结尾、长度为$j$的贡献就是$x.len[j]=prefix.len[j-1]$。因为,$x$可以连在前面所有数的后面,长度+1。
复杂度为$O(nmlog(n))$。
AC代码
1 |
|