可以用DP做。
将点按照X为第一关键字，Y为第二关键字排序
F[i][j]表示1—j个点中加i个矩形面积的最小值
s[i][j]表示覆盖i-j矩形的面积
f[i][j]=max{f[i-1][k]+s[k+1][n]}
但是最后一个点过不去不知道为什么

所以一开始看错题解了。。。。。。 (╯‘□′)╯（┻━┻

KMP模版题（我这个是未改进next函数的KMP，即MP算法，在<训练指南>里有提到）

行，这题目还好

回复 @cstdio :
我是蒟蒻，怎么可能觉得水，我是觉得斯坦纳树太神了不会做，发现可以卡常数过去（明显就是乱搞）
不乱搞题是因为最近好像得了手残+脑残光环，交题10次（10次是少的）内定不过，现在攒题攒了好几道

第一次用long long double 提交居然提示错误

回复 @Will :
放眼望去全是贴的代码啊……
另，已把栈和队列的标签去掉

回复 @Chenyao :
啊……神犇为何这么热衷于发布题解……是因为嫌题太水懒得秒了吗……

回复 @Chenyao :
犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇

恩，果然超时了

手残党的胜利！！！把100000打成1000

看到有个标签是队列和栈，不明觉厉，有人能贴下代码不？

floyd求出任意两点间最短路,最优解的情况一定是两个人到一个点汇合,之后从这个点到另一个点于第三个人汇合,之后到达终点.或者三个人直接到一个点汇合,到达终点....计算下应该可以卡过去(斯坦纳树能吃么?)

@bigmingod
呵呵

回复 @雪狼 :
我强迫症打代码打的也慢

飞机如果飞到一个农场就停一下也没有关系,算法过程就是模拟飞机到每个机场都停一下,该下飞机的奶牛下飞.如果有空位,就让奶牛全部上去,如果上不去,这个时候看飞机上有没有目的地比该牧场的奶牛远的,如果有,凭什么满足目的地远的奶牛,(越近越有可能满足尽量多的奶牛),就给这头奶牛"踢回家",让目的地近的上来.可以用大根堆维护.

回复 @cstdio :
用到KM的副产品的题好像多了起来.....我不会KM!!!!

回复 @ranto :
你妹的,名字还拼错了==

好坑爹，我的老师从来都是要我们自己写排序算法的，我就看到用C++的同学全是直接一个调用函数就解决问题了。。我苦逼的写了个冒泡排序，于是就悲剧了。。不过时间限制是1s，我的冒泡花了1.089s还是过了是什么情况？

不要读错题......