/ Vijos / 题库 / 旅行商简化版 /

题解

122 条题解

  • 0
    @ 2008-10-22 19:27:53

    这道题目，实在郁闷，刷掉我多少AC率！！

    特别提示:1、动归式n,n的特殊处理是for p:=1 to n-1 dos[n,n]:=min(s[n,p]+dist(p,n))2、题目没告诉你它给的数据是排过的！所以你要排序！！3、所有存小数的类型全部是real;所有存整数的类型是longint(及以上)；否则会不过，而且很费解！！

    为我的AC率默哀，虽然我已经不太在乎了！！编译通过...├ 测试数据 01：答案正确... 0ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 0ms├ 测试数据 05：答案正确... 0ms├ 测试数据 06：答案正确... 0ms├ 测试数据 07：答案正确... 0ms├ 测试数据 08：答案正确... 0ms├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 0ms-------------------------Accepted 有效得分：100 有效耗时：0ms

  • 0
    @ 2008-10-13 17:24:07

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2008-10-09 10:55:24

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2008-09-30 14:21:41

    好题

  • 0
    @ 2008-09-30 10:30:57

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2008-09-24 19:46:18

    解题报告http://plfxy.blog.hexun.com/23513580_d.html

  • 0
    @ 2008-09-16 21:39:56

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    真小看了答案，以为最大不会超过99999999……真是教训啊！！

  • 0
    @ 2008-09-16 20:54:21

    编译通过...

  • 0
    @ 2008-09-11 20:06:49

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2008-09-07 13:31:15

    1.正如楼上说的，不过，还有点改进。

    for i:=1 to n do

    　　 begin

    　　　　 for j:=1 to i-1 do

    　　 if (j=i-1)and(j1) then

    　　　　 begin

    　　　　　　　　min:=1e24;

    　　　　　　　　for k:=1 to j-1 do

    　　　　　　　　if f+d

  • 0
    @ 2008-09-07 12:30:31

    正如caray521所说，，

    虽然我不懂，可是看了之后懂！

    我一样骄傲！！

    没有任何遗憾！

  • 0
    @ 2008-09-03 23:58:56

    编译通过...

    ├ 测试数据 01：答案错误...　├ 标准行输出 25.58

    　├ 错误行输出 28.03

    ├ 测试数据 02：运行时错误...| 错误号: 207 | 无效浮点运算

    ├ 测试数据 03：运行时错误...| 错误号: 207 | 无效浮点运算

    ├ 测试数据 04：运行时错误...| 错误号: 207 | 无效浮点运算

    ├ 测试数据 05：运行时错误...| 错误号: 207 | 无效浮点运算

    ├ 测试数据 06：运行时错误...| 错误号: 207 | 无效浮点运算

    ├ 测试数据 07：运行时错误...| 错误号: 207 | 无效浮点运算

    ├ 测试数据 08：运行时错误...| 错误号: 207 | 无效浮点运算

    ├ 测试数据 09：运行时错误...| 错误号: 207 | 无效浮点运算

    ├ 测试数据 10：运行时错误...| 错误号: 207 | 无效浮点运算

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

    Unaccepted 有效得分：0 有效耗时：0ms

    在我家 样例就能是25.58啊。

    我试过real、double。

  • 0
    @ 2008-09-01 17:25:31

    遗憾的是非原创的，不遗憾的是我学到了

    for i:=1 to n do

    begin

    for j:=1 to i-1 do

    if j=1 then

    f:=f+d else

    if j=i-1 then

    begin

    min:=1e24;

    for k:=1 to j-1 do

    if f+d

  • 0
    @ 2008-08-31 17:15:31

    楼上的x1 x2表示什么？dist是什么？

  • 0
    @ 2008-08-27 16:31:21

    这个题就是赤裸裸的Bitonic Tour问题了。我的解决方案如下:

    将一个人从最左端走到最右端，然后从最右端走到最左端等价成两个人同时从最左端不重复的走过中间的点并且到达最右端。

    我们不妨设这两个人为A和B，且总是假定走在前面的人是A。再设函数F(x1, x2)表示A走到x1的位置，B走到x2的位置，并且所有x1，x2之前的位置都被不重复的走过的最短距离之和。根据前面的假设我们可以知道 x1>=x2，且F(xn,xn)即为所得。

    下面的过程就是如何推导出状态方程,我把它划分为三种情况:

    1) 如果x1=x2，即A和B处在同一点，那么F(x1, x2) = F(x1, x1) = F(x1, x1 - 1) + dist(x1, x1 - 1)

    2) 如果x1=x2+1，即B在A的紧邻的靠后一点，那么F(x1, x2) = F(x2, x') + dist(x1, x') (1

  • 0
    @ 2008-08-14 17:46:12

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    无语..........

    第一次用O(N^2)的排序，竟然TLE了

    用QSORT就能秒杀？疑惑.....

    时间级别不是还是O(N^2)吗，常数很小吧

  • 0
    @ 2008-08-08 13:49:11

    实数不能用single，要用double

  • 0
    @ 2008-08-06 19:06:16

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    如何输彩字？用Ubb吗？

  • 0
    @ 2008-07-15 12:03:33

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    为啥sqrt不能对extended用？

  • 0
    @ 2007-12-16 12:46:05

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    5555,由于符点运算的XX错误

    我CE了2次,WA了2次....

旅行商简化版

信息

ID
1014
难度
6
分类
动态规划 点击显示
标签
(无)
递交数
2908
已通过
881
通过率
30%
被复制
17
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1