问题标题: 洛谷：请问洛谷1034 矩形覆盖怎么做？

错误的算法主要是没有考虑到二维平面与一维直线的区别。即如果本题是一维的，给定一个点的序列，求最小的区间长度覆盖所有点且区间不能相交。那么将点排序后枚举划分或是dp都是正确的，因为这样的区间一定是连续的。而在二维平面中，最优解在x轴方向或y轴方向都可能不是连续的（只是这样的数据可能需要特殊构造），所以把点按x排序或y排序或者先按x排序在按y排序都是不对的。如果你真的想排序，官方题解给出一种正确做法是按点到原点连线的极角排序，然后dp。即便是这样，也要先按x dp，在按y dp。但是对于这道题，完全没有必要写dp，既然是搜索，那就暴力枚举每个点在哪个矩形里，在判断是否合法即可，虽然根据数据范围这样是过不了的，但数据已经弱到一定程度了，所以不加任何剪枝就能AC。顺便提醒一下大家，在考试中如果判断暴力过不了，而想到一些不太对但很快的算法，可以把小的数据用暴力，大的用没有把握的算法。这样能尽量多拿分。但是在平常练习中一定要保证解题的正确性，写题解时更应如此，我们写题解是为了帮助他人，同时使自己对知识的掌握更牢固，但如果题解是错的，不仅会让自己记住错误的结论，还会给别人带来麻烦。建议大家可以去看一下官方题解，有一些思路还是值得借鉴的。

其实这题一开始看到有很多奇怪的思路……

1.动态规划F[I][J]，表示处理到第i个点已经形成j个矩形了的最小值……这时候DP记一个路径技能完成转移。复杂度完全可以。懒得写。。。

2.看到k那么小……分治都不想了，好吧其实和动态规划差不多，一直二分区间，然后递归计算答案再合并区间答案（动态规划递归版……有点像线段树合并区间答案……不过要复杂点）。。。

3.再想想其实……暴力50^4也是完全可以接受的……暴力枚举相邻矩形位置（属于左边还是右边随便你→_→），最后就变成区间里RMQ的问题……本来想写线段树耍一耍……发现自己zz了……没有动态修改ST表方便多了。。。然后其实……n<=50.。。。log50与50其实……差个常数。。数据水的话……暴力RMQ都能直接过所以……不多说了……(PS下面题解cpp的一个搜索剪纸写的蛮不错的。。比那位写ST表的童鞋可读性强多了……[捂脸])