题解 - Vijos

0
Killua LV 3 @ 2008-11-10 20:04:18

写了N久~还好AC了~
0
Fengyunfly LV 8 @ 2008-11-04 21:52:28

郁闷..过程中局部变量没有赋初值..搞了好久..
0
吴豪 LV 8 @ 2008-10-29 16:18:42

可以用乘积最大的方法DP.

第一次以x为第一关键字y为第二关键字

第一次以y为第一关键字x为第二关键字

以上
0
Ark Xu LV 3 @ 2008-10-21 22:51:05

用乘积最大的模型

分别进行横向纵向DP

O(n^2*k)
0
fammiebright LV 9 @ 2008-10-06 13:23:05

被***|骗了。我原来一直以为这道题要枚举每个矩形的相对位置然后把点按照相对位置分开。。。
0
ssfzjnsd LV 3 @ 2008-09-17 14:41:22

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

10000

4 4

9 10

15 15

50 156041
0
voyagec2 LV 10 @ 2008-08-19 08:59:17

4个字:扩大矩形
0
鸽子 LV 3 @ 2007-11-12 06:54:26

好失败...初值赋小了.....复制的时候忘记修改了..大家谨记这些错误啊..

思路：枚举每个点在哪个矩形，在新建矩形不重合的情况下计算总面积，与原有总面积进行比较。

实现：DFS
0
lonelycorn LV 3 @ 2007-11-04 22:31:20

公布的标程写了9KB，也只是写了k=1,k=2,k=3的情况

我写了相当委琐的DFS竟然AC了……

枚举每个点放再哪个矩形内，几乎没加剪枝，而且比标程快，也只有97行。
0
XM LV 3 @ 2007-10-29 23:41:57

第3个点

. .

.

. . .

.

. .

要考虑不能重合
0
subrays LV 5 @ 2007-10-10 09:45:45

一次通过..还是搜王道
0
fengyi LV 9 @ 2007-09-20 15:20:46

不错的题目~~

一节课一次AC

对目前的状态感到满意^_^
0
the_melody LV 3 @ 2007-09-11 21:26:06

可行性剪枝＋最优性剪枝`\这可真是最基本也是最经典的剪枝方法了
0
swxadqecz LV 5 @ 2007-08-06 20:47:03

记得第3个点，要加个判重叠～
0
FDhyc LV 10 @ 2007-07-21 23:12:24

我是第101个AC的-_-b
0
print LV 3 @ 2006-11-08 15:03:46

不是如图吗图在哪`\`\``
0
nicolas LV 3 @ 2006-11-01 16:35:01

回下面的朋友

数据是对的，我严格判断了不可重合，也过了这个点。

解法的框架是简单的

但几个子程序却得画几下才能既对又高效

不过数据看起来不难，DFS也能全部0ms
0
为什么封我号？ LV 3 @ 2006-10-22 10:27:57

第三个数据点有误！我偷出来的

题目要求矩形必须完全分离但output是顶点重合的。

cheat吧
0
渴望奔跑的鱼 LV 3 @ 2006-10-04 13:34:10

同意ycglovewxx的观点。。DFS+可行性剪枝+最优性剪枝
0
ycglovewxx LV 3 @ 2006-08-09 09:14:31

深搜+剪枝;

搜索每个点属于第几个矩形,

搜索过程中使每个矩形不断变大,判断有无出现相交的情况,或者当前面积已经大于目前最优解.....

ID

1126

难度

4

分类

搜索 | 搜索与剪枝点击显示

标签

递交数

已通过

556

通过率

40%

被复制

12

上传者