DAY 13

更多的DP优化！！！！！

1.斜率优化

模板题：平面中有 n 个点(xi,yi) ，有 m 条直线，斜率 k 已经确定，需要在给定的 n 个点中，选出一个点 (x,y) ，使得 kx+y 最大。

方法：令两点A（x1,y1),B(x2,y2),kx1+y1>kx2+y2(x1>x2)

所以-k<(y1-y2)/(x1-x2)即-k -k>kBC,所以维护向上凸的凸包，满足单调性，二分（还没加上DP）

加上DP：土地并购

Kano准备扩大他的农场，眼下必须购买N块长方形土地。如果Kano买一块土地，价格就是土地的面积。他也可以选择并购多块土地，并购的价格为这些土地中最大的长乘以最大的宽，比如Kano购买3×5和5×3的土地，只需要支付5×5=25元，比分开买合算。请你帮他计算购买所有土地的最小费用。

易知，当一块地长宽都小于等于另一块地的时候没贡献，所以先去掉

怎么去？先以长（或宽）为关键降序排序，省去一维，接下来的点的Y值应该升序

然后就会发现一段区间的并购价值就是第一个的长*最后一个的宽，就可以愉快DP了

2加数据结构：常用的就是线段树等，思维难度不大，主要考察数据结构应用

决策单调性：最远点

给你一个N个点的凸多边形，求离每一个点最远的点。

不好说，上图

如图，红点为一组最远点，则蓝点的最远点在异侧

所以每次先算中间点的最远点，就可以缩小一半范围，就是nlogn