64 条题解

  • 0
    @ 2009-07-01 20:22:57

    实践证明——的确很easy!

    我和楼下牛们的思路有些不一样:

    f[i][j][k]表示:第一辆车到达i,第二辆车到达j,第三辆车到达k时的最小距离。

    (并不一定i

  • 0
    @ 2009-06-30 18:50:10

    数据太弱

    鉴定完毕

  • 0
    @ 2009-06-17 19:02:38

    AC 标程,仅供参考。

    谢谢。

    编译通过...

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

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

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

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

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

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

    program P1547;

    const

    mm =2139062143;

    var

    ans :array[1..100,1..100,1..100]of longint;

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

    dis :array[1..100,1..100]of longint;

    function maxin(a,b,c:longint):longint;

    begin

    if (a>=b) and (a>=c) then exit(a);

    if (b>=a) and (b>=c) then exit(b);

    if (c>=b) and (c>=a) then exit(c);

    end;

    procedure search(a,b,c:longint);

    var

    i,j :longint;

    begin

    i:=maxin(a,b,c);

    if (i=n) and (ans[a,b,c]ans[a,b,c]+dis[a,i+1]) then begin ans:=ans[a,b,c]+dis[a,i+1]; search(i+1,b,c); end;

    if (ans[a,i+1,c]>ans[a,b,c]+dis) then begin ans[a,i+1,c]:=ans[a,b,c]+dis; search(a,i+1,c); end;

    if (ans[a,b,i+1]>ans[a,b,c]+dis[c,i+1]) then begin ans[a,b,i+1]:=ans[a,b,c]+dis[c,i+1]; search(a,b,i+1); end;

    end;

    begin

    readln(n);

    for i:=1 to n do

    for j:=i+1 to n do read(dis);

    fillchar(ans,sizeof(ans),127); max:=maxlongint;

    ans[1,1,1]:=0;

    search(1,1,1);

    writeln(max);

    end.

  • 0
    @ 2009-06-16 20:28:45

    樓下的做法就對,但是把W數組從-2開willy很不理解。

  • 0
    @ 2009-06-15 07:28:32

    不知道自己写的算不算Dp,望大家指点

    program xing;

    var

    w:array[-2..100,-2..100] of longint;

    f:array[1..100] of longint;

    v:array[1..100] of integer;

    i,j,min,n,l:longint;

    begin

    readln(n);

    for i:=1 to n-1 do begin

    for j:=i+1 to n do

    read(w);

    readln;

    end;

    v[1]:=3;

    for i:=2 to n do begin

    min:=maxlongint;

    l:=0;

    for j:=1 to i-1 do

    if (w[j,i]0) and (v[j]>0) and (w[j,i]

  • 0
    @ 2009-06-13 17:58:55

    才4个数据……

    DP乱搞搞就AC了……

  • 0
    @ 2009-06-11 13:22:20

    忘记初始化了,样例输出2

    赋值为maxlongint才过

  • 0
    @ 2009-10-26 18:54:59

    我是这么写的。AC0MS

    呃 为什么改了题解 我就是最后一个写题解的人了

    编译通过...

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

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

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

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

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

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

    dp[i][j][k]表示三台车子所在位置, 降序排列。

    那么dp[i][j][k]=dp[m][j][k]+d[m][j+1]+d[j+1][J+2]+...+d[i];

    d[j+1][J+2]+...+d[i] 这部分可以写函数dis(J+1,i)。

    关键代码:

    if(m

  • 0
    @ 2009-06-05 18:39:08

    编译通过...

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

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

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

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

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

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

    f[i][j][k] : 最快的车在i城市,第二快的在j城市,第三快的在k城市的最小费用。

  • 0
    @ 2009-06-04 16:50:00

    个人认为题目较难理解!

    我的做法和WJ的做法一样,虽然过得了,可是好像有反例:

    6

    1 1 1 2 33

    1 33 33 33

    33 33 33

    33 33

    1

    自己的程序输出为69,而正确答案应该是38.

    解释:第一辆车:1-2-3,总路程为2.

    第二辆车:1-4,总路程为33.

    第三辆车:1-5-6,总路程为3.

    所以最优的方案应该是38.

  • 0
    @ 2009-06-04 09:23:24

    初学者,请教问题:

    第I行,有I-1个数 是"第2行,有1个数"的意思吗?

    但样例中第2行有4个数,不知如何理解?

    是否是这样的意思:第I行,有N-I+1个数?

  • 0
    @ 2009-06-03 16:36:12

    枚举每一个城市

    将所有含有上一城市的状态进行递推

    最后寻找含有最后一城市的最小值输出

  • 0
    @ 2009-06-03 16:28:03

    个人感觉楼下的做法相当妙..

    比用三维数组的做法好很多..

  • 0
    @ 2009-06-03 16:10:22

    用f[i]表示去前i个城市的最短距离,v[i]表示第i个城市当前的车的数量,初始时,

    v[1]=3,状态方程就是f[i]:=f+min(a[j,i]),{j:=1 to i-1},另外注意一下数组v的处理就可以了,只有当一个城市有车时才能前往下一个城市!

    总感觉自己的程序不太完善,不过还是能AC。。。数据弱?

  • 0
    @ 2009-06-05 15:09:32

    3维的如何做啊

  • 0
    @ 2009-06-03 12:53:01

    水。。。。

  • 0
    @ 2009-08-02 15:42:29

    很简单啊,哪来的3维DP,我用很基础的DP就A啦

  • 0
    @ 2009-06-03 09:28:24

    编译通过...

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

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

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

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

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

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

    雅婷的通过率挺高嘛

  • 0
    @ 2009-06-02 21:35:45

    在座的都是大牛啊(除了饿)……我也看看

    看懂了!

    所有人从1市出发,共三辆车

    第一辆车去2市(路程1)

    第二辆车去3市(路程1)

    第三辆车去4市(路程1)

    突然发现,还有一个市没去!

    题目说不走回头路(不能从2、3、4市直接回到一市)

    只好从2、3、4市中任选一辆开往五市(路程都是33)

    33+1+1+1=36

    完美解决

  • 0
    @ 2009-06-03 18:44:26

    原来是这个意思...

    标题好强的说

信息

ID
1547
难度
1
分类
搜索 | 记忆化搜索 点击显示
标签
(无)
递交数
884
已通过
590
通过率
67%
被复制
5
上传者