/ Vijos / 题库 / 蚱蜢 /

题解

15 条题解

  • 0
    @ 2010-03-13 21:11:20

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    险过!

  • 0
    @ 2009-10-08 17:36:04

    program zha_meng;type node=record wh,zhi:longint; end;const maxn=1502;dx:array[1..2]of -1..1=(-1,1);var i,j,k,l,m,ffff,nn,n,sn,x,y,sj,sm,max,u,v:longint; c:array[0..maxn*maxn,0..2]of longint; a:array[0..maxn,0..maxn]of longint; heng,lie:array[0..maxn,0..4]of node; temp,xxxx:node; yes:boolean;procedure sort(l,r:longint);var i,j,x:longint;begin i:=l; j:=r; x:=c[(l+r)shr 1,0]; repeat while cx do dec(j); if ij;if l

  • 0
    @ 2009-10-08 14:43:27

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

    维护每行每列前4优的解

    why?

    lx大牛说的很清楚

  • 0
    @ 2009-09-25 22:45:18

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    等待 waiting 队伍!!AC

    算法很简单,先用每一朵花的花瓣数对花排序 记录: 原有位置 花瓣数 最大花朵数

    开两个数组 分别保存每行前四大的花朵 和 每列前四大的花朵(最多三个点不能到达)

    接下来从花瓣数最少的开始DP(每次对花瓣数相同的花进行)

    1:先找它的上一行 下一行 前一列 后一列 中是否有更优解,然后更新

    2:维护更新后的花所在行和列的前4大

    扫描所有结点

    从每行 每列的最大值中取最大 既答案!!

  • 0
    @ 2009-07-29 09:46:50

    膜拜ORZ Cgy

    虽然下滑了一点通过率,但是做了这题我又对DP有了新的见解,真是融会贯通啊!!!

  • 0
    @ 2009-07-24 14:21:08

    Orz cgy

  • 0
    @ 2009-07-24 12:56:20

    看了大牛的讲解深受启发

  • 0
    @ 2009-07-23 21:24:51

    发题人说两句吧:

    此题的基础算法时间复杂度为O(n^3),可以勉强过5个点。

    标程的算法貌似是保存每行每列的四个最优值……

    讲得很模糊,cg4ever神牛讲的还算细致:

    “按叶片数排序后来做

    容易想到的是树状数组,一共开 4 * N 个大小是 N 的.

    不过这样会造成MLE,更重要的是后两个点过不了.

    而更优的解法是记录每行每列的最优的4个值,这样就可以过了。”

    题目很难做,大家耐心做哦~

  • 0
    @ 2009-07-23 21:04:03

    用递归做,但全错

    附代码:

    var a:array[1..1500,1..1500] of longint;

    i,j,l,m,n,max:longint;

    procedure ss(q,w,e,r:longint);

    var f:longint;

    begin

    if (q>n) or (qn) or (w

  • 0
    @ 2009-07-25 07:16:20

    OoRz Cgy

    虽然算法不是原创的

    但是发现我时间最短啊,4702MS

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    算法虽然是线性的

    但常数实在太大

    MAXN=1500

    复杂度是O(MAXN*MAXN*4*4)

    但是有不少取最大,更新步骤,时间就上去了

    ==试下保存3优的

  • 0
    @ 2009-07-23 17:21:17

    Orz 神牛题!

  • 0
    @ 2009-07-23 16:48:54

    好像在OIBH月刊上看到过

  • 0
    @ 2009-07-23 23:12:16

    树状数组开4N发现过不了于是囧了。。

    然后可以发现其实只要保存每行每列前4优即可。

    总共写了500行。从C++到pas。。貌似N^2logn被我优化到极限了。。

  • 0
    @ 2009-07-23 16:19:23

    我的天……最后俩数据太大了

  • 0
    @ 2009-07-23 15:50:01

    站地下室吧

  • 1

信息

ID
1586
难度
8
分类
动态规划 | 数据结构 点击显示
标签
(无)
递交数
312
已通过
46
通过率
15%
被复制
2
上传者