题解

25 条题解

  • 0
    @ 2014-10-25 07:15:49

    优先队列

  • 0
    @ 2009-10-08 14:36:57

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

    水题啊

    f(i)=f(j-1)+sum(i)-sum(j)+dis(i)+dis(j)

    sum(i)表示 从0一直走到i的长度

    dis(i)表示从(0,0)到i点的距离

    o(n^2)复杂度貌似很高

    用单调队列,秒杀!!!

    貌似不优化也可以秒杀

    好题啊,数据太水了

  • 0
    @ 2009-07-16 20:55:22

    单调队列编不对,没办法还得O(N^2).

  • 0
    @ 2009-07-14 16:08:12

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

    不知道那单调性...用树状数组维护的最小值.

  • 0
    @ 2009-07-14 14:00:32

    Orz tracy-henry神牛。

  • 0
    @ 2009-07-14 13:30:39

    O┬L

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

    楼下的,那个神牛宋文杰是你搞的吧……

  • 0
    @ 2009-07-14 12:51:53

    Orz宋文杰

    srO宋文杰

    OTL宋文杰

  • 0
    @ 2009-07-14 11:16:54

    ......

  • 0
    @ 2009-07-14 11:07:15

    5555

    实在是太晚了。。。

    同意楼下的

  • 0
    @ 2009-07-14 09:36:40

    占个位子啊……

    应该还可以用单调队列做到O(n),但是没想到裸的就AC了……

  • 0
    @ 2009-07-14 08:20:11

    DP+优化

    Voyagec2神牛用两句话剪枝替我的堆.... 膜拜之

  • -2
    @ 2009-07-14 12:17:58

    啊!!有是一个超级无敌五香十八大水题!!!!!!!!!

    这个太水了。。不会做的人都给我回去搞文化课去,搞什么oi啊!!

    这很明显是一个DP的模型:

    我们设计状态:

    用opt[i]表示运输前i个箱子所需最小步数

    用v[i]代表从i走到源点所需的步数

    用x[i]表示从i-1走到i所需的步数,i>1

    用sum[i]代表x[2]+x[3]+...+x[i]

    那么很明显:

    opt[i] = Min(opt[j]+sum[i]-sum[j+1]+v[i]+v[j+1])

    = Min(opt[j]-sum[j+1]+v[j+1])+sum[i]+v[i]

    其中很重要的是b[i]

  • -3
    @ 2009-07-14 13:52:05

    神牛们,教教我这个菜鸟单调队列吧

    虽然这题秒杀......

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • -4
    @ 2009-10-28 13:05:07

    编译通过...

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

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

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

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

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

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

    ├ 测试数据 07:运行超时...

    ├ 测试数据 08:运行超时...

    ├ 测试数据 09:运行超时...

    ├ 测试数据 10:运行超时...

    ├ 测试数据 11:运行超时...

    ├ 测试数据 12:运行超时...

    ├ 测试数据 13:运行超时...

    ├ 测试数据 14:运行超时...

    ├ 测试数据 15:运行超时...

    ├ 测试数据 16:运行超时...

    ├ 测试数据 17:运行超时...

    ├ 测试数据 18:运行超时...

    ├ 测试数据 19:运行超时...

    ├ 测试数据 20:运行超时...

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

    Unaccepted 有效得分:30 有效耗时:1390ms

    srO自己

  • -4
    @ 2009-09-24 13:47:35

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    水的单调队列

    通过   38人

    提交   99次

  • -4
    @ 2009-09-23 07:35:29

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    25分钟足矣

  • -4
    @ 2009-09-08 17:00:55

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    单调队列

  • -4
    @ 2009-08-07 09:03:16

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    数据太弱了

  • -4
    @ 2009-08-05 20:36:59

    痛苦啊~

    好好的省赛题被套上这么水的数据。

    随便平方都过~

    伤心~~

    【终于编对了“单调队列”(为啥叫单调队列,不叫 维护单调性的双头栈 呢?不明白啊~)】

信息

ID
1573
难度
6
分类
其他 | 排序 点击显示
标签
递交数
402
已通过
116
通过率
29%
被复制
1
上传者