数据已修复 2017/9/4

数据咋回事，倒数第二个改一下

回复 @liu_runda :
666666666666666666666666666666666666666666666666666

这题数据有毒。。。。

倒数第二组的数据是错的，答案应当为124850而非139108，可行方案为
42 16 391 185
94 296 374 359
7 426 389 496
427 11 484 388
即：
矩形1：左下角(42,16)右上角(391,185)
矩形2：左下角(94,296)右上角(374,359)
矩形3：左下角(7,426 )右上角(389, 496)
矩形4：左下角(427,11)右上角 (484,388)
可以验证,这组方案是合法的。

倒数第二个点过不了。。很奇怪的说

将点按x为第一关键字，y为第二关键字，递增排序。f[i][x1][x2]表示 由点 x1到点 x2范围之内分成 i 个矩形所用的最少面积。这样应该没问题。

偶，不对，这样好像k=4的时候有反例，还是搜索吧！

回复 @HouJikan :
x，y两遍还是会有问题的- -可以卡掉
例如这个数据：
8 4
0 0
10 1
8 10000
9 10001
1000 3
1001 4
10000 2
10001 7
显然最优解释是1,2一组，3,4一组，5，6一组，7,8一组
最优解为：17
而你的代码显然不能处理- -事实上也是这样，你跑出来是10000+ - -

回复 @HouJikan :
这个显然不对把……
比如这4个点用两个矩形覆盖：
(1,0)、(2,100)、(3,1)、(4,101)
显然最小答案是4。但是你的算法会得出200……

可以用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]}
但是最后一个点过不去不知道为什么

最后一个点和答案差几十 = =....................扯淡啊

裸的爆搜啊= =...... 只过了n<=3的....n=4的还没调出来QAQ

纯搜索应该可以过6组。
前5组原数据没有K=4的情况。
所以纯搜索O（N^3）=125000完全可以过。
但是第6组极限数据理论值为o(n^4)就过不去，需要剪枝？
第7组是K=4，可能是数据比较巧，搜索也能过。
第6组怎么做？

纯搜索+少个判断函数 过3组...