题解

68 条题解

  • 0
    @ 2009-07-24 14:11:26

    样例为什么是80???!!!

    应该是90!

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

  • 0
    @ 2009-07-19 14:43:18

    编译通过...

    ├ 测试数据 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达成,自我庆祝一下

  • 0
    @ 2009-07-14 16:53:33

    极大化处理

    没有0Ms!!

    5555555555

  • 0
    @ 2009-07-14 16:46:21

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

    怎么处理?

    无视掉]

    还是]

    拖出去]

    弹]

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

  • 0
    @ 2009-06-10 15:41:09

    编译通过...

    ├ 测试数据 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加剪枝。。。。。。

  • 0
    @ 2009-03-28 19:28:12

    编译通过...

    ├ 测试数据 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,看来这个方法不好啊。

  • 0
    @ 2009-03-16 20:26:14

    极大化思想

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

  • 0
    @ 2009-02-14 19:33:32

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

    做法是

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

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

  • 0
    @ 2008-11-13 13:54:13

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

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

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

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

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

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

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

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

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

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

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

    好危险的时间啊~~~

  • 0
    @ 2008-11-07 07:58:48

    编译通过...

    ├ 测试数据 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了!

  • 0
    @ 2008-11-06 20:11:19

    16

  • 0
    @ 2008-11-04 21:37:49

    给个数据

    大家报下答案.

    5 5

    2

    3 4

    4 3

  • 0
    @ 2008-10-29 20:34:01

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

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

  • 0
    @ 2008-10-04 17:57:30

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2008-10-04 15:58:14

    编译通过...

    ├ 测试数据 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)算法

  • 0
    @ 2008-09-27 19:27:09

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

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

  • 0
    @ 2008-09-20 19:35:37

    编译通过...

    ├ 测试数据 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了。。

  • 0
    @ 2008-10-23 14:18:53

    编译通过...

    ├ 测试数据 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.

  • 0
    @ 2008-09-15 17:25:28

    编译通过...

  • 0
    @ 2008-09-09 16:13:32

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

信息

ID
1055
难度
5
分类
动态规划 点击显示
标签
递交数
2106
已通过
653
通过率
31%
被复制
10
上传者