HDU1025 – Constructing Roads In JGShining’s Kingdom

这是一个经典的LIS问题的数据强化。原型题我曾经在NOIP的复赛书上看见过,我们需要把第一维从小到大排序,然后求第二维的LIS,这样就可以保证不相交。这里需要优化转移过程。

我们知道常见的LIS的转移方程是$opt[i] = \max \{opt[j] | 1 \leq j < i, a[i] > a[j] \} + 1 $。朴素的实现需要$O(n^2)$的渐进时间复杂度。对于这一题$5 \times 10^5$ 级别的数据是行不通的,考虑优化。

详见刘汝佳蓝书p62,大意如下。

如果$a_i = 2$,$a[j] = 6$,$opt[i] = opt[j]$,那么由$i$转移到的点一定比由$j$转移到的优。因为如果有一个点$k(k > \max \{ i, j \})$,当$a_k>a[j]$($j$可以转移到$k$)时候,$i$一定可以转移到$k$,但是$i$可以转移到$k$的时候,$j$不一定可以。

我们需要用一个数组维护当前找到的LIS是什么,然后看当前的$a_i$可以被放在LIS的哪个位置。假设当前的$a_i = 5$,当前的LIS为$[1,3,4,7]$,那么$a_i$一定可以放在LIS的第四个位置,对应的LIS的长度是4,我们把7换成5,维护最小的值。(可能这里这里讲的不是很清楚,建议看蓝书或者手动模拟这个过程)

以上的操作可以用二分查找实现,扫描完$a_i$数组之后得到了LIS的长度,还能得到LIS。优化的方法其实不只有这一种,待后续更新。

 

说点什么

avatar
50
  Subscribe  
提醒