样例为什么是80？？？！！！

应该是90！

矩形左上角(1,1)，右下角(10,9)

编译通过...

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

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

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

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

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

├ 测试数据 06：答案正确... 150ms

├ 测试数据 07：答案正确... 103ms

├ 测试数据 08：答案正确... 150ms

├ 测试数据 09：答案正确... 134ms

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

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

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

尽管不是0MS,但是……本人的第60个AC达成，自我庆祝一下

极大化处理

没有0Ms！！

5555555555

有某人傻到直接for i,j=1 to L,W

怎么处理?

无视掉]

还是]

拖出去]

弹]

Boom..Boom像弹棉花一样清脆悦耳哦~

编译通过...

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

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

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

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

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

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

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

├ 测试数据 08：答案正确... 41ms

├ 测试数据 09：答案正确... 41ms

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

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

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

N^2加剪枝。。。。。。

编译通过...

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

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

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

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

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

├ 测试数据 06：答案正确... 291ms

├ 测试数据 07：答案正确... 212ms

├ 测试数据 08：答案正确... 275ms

├ 测试数据 09：答案正确... 275ms

├ 测试数据 10：答案正确... 25ms

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

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

。。。分下边界和x轴有无相接考虑,加上move和O(N^2)DP,看来这个方法不好啊。

极大化思想

可以参考WC2003wzk论文,写的很好

脑残的又把调试输出交上去了..

做法是

把所有点加上4个顶点按横坐标排序

然后枚举左边界,向右拓展,随时调整上下边界,当UP

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

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

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

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

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

├ 测试数据 06：答案正确... 999ms

├ 测试数据 07：答案正确... 999ms

├ 测试数据 08：答案正确... 999ms

├ 测试数据 09：答案正确... 999ms

├ 测试数据 10：答案正确... 999ms

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

好危险的时间啊~~~

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

Ho~Ho~ o(s^2)加上剪枝就0s了！

16

给个数据

大家报下答案.

5 5

2

3 4

4 3

有人比我更菜么？此题我做了四天，先后提交了N多次，得分10到50都有，最后A了，而且A的稀里糊涂……

我想问一下是不是评测机有问题？这个题我从开始一直是用取中快排，老是WA，最后改成随机快排就对了，然后重新试了试取中快排居然又对了，怎么回事？

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

最优子矩形O(S^2)算法

DP。数据类型longint，否则要挂掉。

我的代码在http://dfs35123.spaces.live.com/blog/cns!6CB032EC0980F16!374.entry

编译通过...

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

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

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

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

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

├ 测试数据 06：答案正确... 447ms

├ 测试数据 07：答案正确... 400ms

├ 测试数据 08：答案正确... 603ms

├ 测试数据 09：答案正确... 541ms

├ 测试数据 10：答案正确... 119ms

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

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

用Temper测的。。时间好久。。

看wzk2003论文吧。一开始我用方法二，结果严重超时。。后来改方法一，Ac了。。

编译通过...

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

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

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

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

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

├ 测试数据 06：答案正确... 228ms

├ 测试数据 07：答案正确... 322ms

├ 测试数据 08：答案正确... 369ms

├ 测试数据 09：答案正确... 369ms

├ 测试数据 10：答案正确... 103ms

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

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

........................................

Ft... 看来后面的测试点的牛还是很多的....早知道些N*M内算法了...

编译通过...

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

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

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

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

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

├ 测试数据 06：答案正确... 119ms

├ 测试数据 07：答案正确... 134ms

├ 测试数据 08：答案正确... 166ms

├ 测试数据 09：答案正确... 197ms

├ 测试数据 10：答案正确... 25ms

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

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

换了测试机 就是不一样!!!!

Program CowBath;

Const

Maxn = 30100;

Type

Arr = Record

x, y: Longint;

End;

Var

G: Array [0..Maxn] Of Arr;

P: Array [0..Maxn] Of Longint;

B: Array [0..Maxn] Of Boolean;

i, j, k, n, m, s, L, r, x: Integer;

Ans, Max1, t: Longint;

Function Max(a, b: Longint): Longint;

Begin

If a > b Then Max := a Else Max := b;

End;

Procedure QuickSortG(l, r: Integer);

Var

i, j: Integer;

y, x: Arr;

Begin

i := l;

j := r;

x := G[(l + r) Div 2];

Repeat

While G[i].y < x.y Do Inc(i);

While G[j].y > x.y Do Dec(j);

If i j;

If l < j Then QuickSortG(l, j);

If i < r Then QuickSortG(i, r);

End;

Begin

Ans := 0;

ReadLn(n, m);

ReadLn(s);

For i:= 1 To s Do Read(G[i].x, G[i].y);

QuickSortG(1, s);

For i:= 1 To s Do Begin

L := 0;

r := n;

For j:= i+1 To s Do If G[i].y G[j].y Then Begin

Ans := Max(Ans, (G[j].y - G[i].y) * (r - L));

If (G[j].x l) Then l := G[j].x;

If (G[j].x >= G[i].x) And (G[j].x < r) Then r := G[j].x;

End;

Ans := Max(Ans, (m - G[i].y) * (r - l));

End;

FillChar(B, SizeOf(B), False);

k := 2;

P[1] := 0;

P[2] := n;

B[0] := True;

B[n] := True;

Max1 := n;

For i:= 1 To s Do Begin

Ans := Max(Ans, Max1 * G[i].y);

If Not B[G[i].x] Then Begin

x := k;

While P[x] >= G[i].x Do Dec(x);

t := x + 1;

For j:= k DownTo t Do P[j + 1] := P[j];

P[t] := G[i].x;

Inc(k);

B[G[i].x] := True;

Max1 := 0;

For j:= 1 To k-1 Do Max1 := Max(Max1, P[j + 1] - P[j]);

End;

End;

Ans := Max(Ans, Max1 * m);

WriteLn(Ans);

End.

编译通过...

编译通过...

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

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

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

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

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

├ 测试数据 06：答案正确... 369ms

├ 测试数据 07：答案正确... 338ms

├ 测试数据 08：答案正确... 525ms

├ 测试数据 09：答案正确... 509ms

├ 测试数据 10：答案正确... 103ms

汗，王知昆论文果然强，一看便知。。。。

不过有点慢，不知道楼下的牛人怎么写的