hdu 1950 Bridging signals (LIS)

题目链接
题意:有两跟柱子并排竖直放置,每根柱子有n个结点,从上往下标号1..n, 两根柱子间的结点间要连线,给出计划连接的情况。a[i]表示左边结点i连接右边结点a[i].但是要求连线不能交叉,所以计划可能不能全部执行。现在问最多能连接多少条线。
思路:由于不能交叉,而左边的结点是按照顺序给出的,所以右边连接的结点只能是越来越大。其实就是求a[i]的最长上升子序列。感觉算是LIS的一个比较巧妙的应用? 由于n还是很大。所以必须nlogn的做法。

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz