單調专题

DP.單調隊列::poj1631 Bridging signals

题目大意:两岸的同等数目的信号灯一一对应,连线,从中找出最多的线出来,它们之间互不交叉。只要求输出最大的线条数。   本题不需要画图了,因为画了图会尝试用二维的DP去做,吃力不讨好,既然输入是一维的一个串,而且该串简洁地包含了全部的信息,那么直接DP何乐而不为呢? 通过对例子(4,2,6,3,1,5)的观察,发现被选中的数字是递增的!再找了一组例子观察,发现同样的规律。那么问题转化为求序列的