bzoj 1537: [POI2005]Aut- The Bus 树状数组

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1537


每个点一定是从它左下角最优的那个转移过来。

按照x为第一关键字,y为第二关键字从小到大排序,用树状数组维护y坐标上的前缀最大值,每次查询一下最大值,再把新的答案放进树状数组更新一下。

最后的答案就是整个树状数组的最大值。

 

发表评论