/ Vijos / 题库 / 过河 /

题解

333 条题解

  • 0
    @ 2008-09-27 21:05:18

    路径压缩，不过当S=T的时候属于特殊情况，不能进行路径压缩。

    F：=Min{F..F}+A

    编译通过...

    ├ 测试数据 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-23 20:32:26

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    一次AC！！！

  • 0
    @ 2008-09-23 20:30:12

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    第一次冒泡时BOOLEAN量初值赋错，浪费一次AC

  • 0
    @ 2008-09-20 13:33:23

    能不能给几个测试数据？

  • 0
    @ 2008-09-19 20:05:14

    {

    HUXIUHAN

    var l,s,t,m,i,j,x,last,delta:longint;

    f,b:Array[0..15000] of longint;

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

    begin

    readln(l);

    readln(s,t,m);

    for i:=1 to m do read(st[i]);

    if s=t then

    begin

    for i:=1 to m do if st[i] mod s = 0 then inc(x);

    writeln(x);

    exit;

    end;

    for i:=1 to m-1 do

    for j:=i+1 to m do

    if st[i]>st[j] then

    begin

    x:=st[i];

    st[i]:=st[j];

    st[j]:=x;

    end;

    for i:=1 to m do

    begin

    x:=st[i];

    x:=x-delta;

    if x-last>72 then

    begin

    delta:=delta+(x-last-72);

    l:=l-(x-last-72);

    x:=last+72;

    end;

    b[x]:=1;

    last:=x;

    end;

    if l-last>72 then l:=last+72;

    for i:=1 to l do f[i]:=maxint;

    for i:=0 to l-s do

    for j:=s to t do

    if f>f[i]+b then f:=f[i]+b;

    writeln(f[l]);

    end.

    }

  • 0
    @ 2008-09-17 08:41:52

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    哇kao!好爽!

    现压缩掉桥的长度, 我是按照82压缩了 其实好像是72貌似就行. 不过没敢冒险!

    然后瞅瞅s和t相等不,如果相等, 直接Rock Mod s 有几个=0的答案就是几了.

    其他时候就是对Rock来下排序, 制作俩数组, 存到这个位置要踩石头 代DP方程Opt[i] := Min(Opt[i - j] + F[i], Opt[i])

    万事大吉!

    Program River;

    Const

    MaxR = 111;

    MaxL = 10020;

    Var

    G, P: Array [0..MaxR] Of Longint;

    Opt, F: Array [0..MaxL] Of Longint;

    n, s, t, m, L, i, j, Ans: Longint;

    Function Min(a, b: Longint): Longint;

    Begin

    If a < b Then Min := a Else Min := b;

    End;

    Procedure QuickSort(l, r: Integer);

    Var

    x, y, i, j: Longint;

    Begin

    i := l;

    j := r;

    x := G[(l + r) Div 2];

    Repeat

    While G[i] < x Do Inc(i);

    While G[j] > x Do Dec(j);

    If i j;

    If l < j Then QuickSort(l, j);

    If i < r Then QuickSort(i, r);

    End;

    Begin

    FillChar(Opt, SizeOf(Opt), 0);

    FillChar(F, SizeOf(F), 0);

    ReadLn(n);

    ReadLn(s, t, m);

    For i:= 1 To m Do Read(G[i]);

    G[m + 1] := n;

    If s = t Then Begin

    Ans := 0;

    For i:= 1 To m Do If G[i] Mod s = 0 Then Inc(Ans);

    End Else Begin

    QuickSort(1, m);

    G[0] := 0;

    G[m + 1] := n;

    For i:= 0 To m Do

    If G[i + 1] - G[i] > 82 Then P[i] := 82 Else P[i] := G[i + 1] - G[i];

    L := 0;

    For i:= 0 To m+1 Do Begin

    L := L + P[i];

    F[L] := 1;

    End;

    n := L + P[m];

    Opt[0] := 0;

    For i:= 1 To n+10 Do Begin

    Opt[i] := MaxInt;

    For j:= s To t Do Begin

    If (i > s) Then Opt[i] := Min(Opt[i - j] + F[i], Opt[i]);

    End;

    End;

    Ans := Opt[n + 10];

    End;

    WriteLn(Ans);

    End.

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

    var

    a:array[0..15000] of longint;

    f:array[1..15000,1..2] of longint;

    n,i,j,kk:longint;

    begin

    readln(n);

    for i:=1 to n do

    readln(f,f);

    for i:=1 to n do

    begin

    kk:=0;

    for j:=1 to n do

    if (ij) and(f[j,1]

  • 0
    @ 2008-09-12 00:09:45

    哇!!!!!!!!!

    激动啊!!!!!!!

    一年前做了一个上午,然后就放弃了;

    一个月前做了两个一半下午,又放弃了;

    几天前开始做,连续好几个晚上,今天终于过了.........

    石子要排序....一年前是这么崩的

    要压缩间隔....一个月前是这么崩的

    然后...简单DP,

    a数组记录到第i个点时最少的踩石子数,

    b数组记录第i个点是否有石子,

    c数组记录是否可以跳到第i个点,

    压缩用2520,(1-10最小公倍数),

    if d[i]-d>2520 then d[i]:=d+(d[i]-d) mod 2520;

    这样压缩即可..........

  • 0
    @ 2008-09-12 08:53:23

    qianyu

    前面qianyu发的算法感觉有些问题,我按照他的算法没有通过.

    初始化时他说:

    预处理f[1，j]的时候，只要判断能否由0跳至s[i]+j，如果不能，则赋为maxint，否则如果是石子就＝1，如果是空地就＝0

    但这是不行的,空地的地方可能是经由踩过一颗石子才达这位置,所以为0就错了.僻如:s=2,t=3;石子的位置是2,3,5,6,7.

    其中桥上4这个位置必须经由2这个位置才能到过,它最少应该踩到一颗石子,而不能初始化为0.

    不知道qianyou是怎么解决这个问题的???

    后来根据他人的样例改进了算法,是通过了,但是我还是发现,在有些位置上最少石子数不对,只是不影响最后的结果,这一点很奇怪,我无法证明它的正确性.

    另一种做法中,以桥上的坐标来动规,可是数组a的大小你们是怎么定义的,桥的长度太大,经过压缩会在什么范围内呢?数组定义成多大,才能适用所有的情况呢??

  • 0
    @ 2008-09-10 20:07:51

    编译通过...

    ├ 测试数据 01：运行时错误...| 错误号: 216 | 存取非法

    ├ 测试数据 02：运行时错误...| 错误号: 216 | 存取非法

    ├ 测试数据 03：运行时错误...| 错误号: 216 | 存取非法

    ├ 测试数据 04：运行时错误...| 错误号: 216 | 存取非法

    ├ 测试数据 05：运行时错误...| 错误号: 216 | 存取非法

    ├ 测试数据 06：运行时错误...| 错误号: 216 | 存取非法

    ├ 测试数据 07：运行时错误...| 错误号: 216 | 存取非法

    ├ 测试数据 08：运行时错误...| 错误号: 216 | 存取非法

    ├ 测试数据 09：运行时错误...| 错误号: 216 | 存取非法

    ├ 测试数据 10：运行时错误...| 错误号: 216 | 存取非法

    各位看看我错哪了，怎么会存取非法？？

    var l,j,i,f,p:longint;

    m,s,t,min,d:integer;

    a,v:array[-10..1300] of integer;

    begin

    readln(l);

    readln(s,t,m);

    fillchar(a,sizeof(a),0); fillchar(v,sizeof(v),0);

    f:=0;p:=0;d:=s*(s-1);

    for i:=1 to m do

    begin

    read(j);

    j:=j-f;

    if j-p-1>d then f:=f+j-p-1-d;

    a[j]:=1;

    p:=j;

    end;

    readln;

    l:=l-f;

    v[0]:=0;

    for i:=-10 to -1 do v[i]:=101;

    for i:=1 to l do

    begin

    min:=1000;

    for j:=s to t do

    if v

  • 0
    @ 2008-09-07 21:49:41

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    绝对经典的好题,即使去年做过一遍,今年还是写了4次才AC..

  • 0
    @ 2008-09-07 09:35:00

    晕，第6个点不过是因为-10--1没置为无穷大。。。

  • 0
    @ 2008-09-05 13:01:55

    压缩处理最重要！！

    记住！

    DP是垃圾！

    for i:=1 to m do //压缩

    if c[i]-c>=72 then

    begin

    a[t1+72]:=true;

    inc(t1,72);

    dec(l,c[i]-c-72);//压缩后要减掉压缩后的长度

    end

    else

    begin

    a[t1+c[i]-c]:=true;

    inc(t1,c[i]-c);

    end;

  • 0
    @ 2008-09-05 11:29:10

    bi:第i个石子坐标

    动规

    a[0]=0;

    对n>=t

    a[n]=min{a[n]+a[n-s],a[n]+a[n-s-1], ...,a[n]+a[n-t]}

    对s=

  • 0
    @ 2008-09-02 21:42:56

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    int s,t,m,l,i,j,st[101],map[2001]={0},l2,k,tm=0,f[2001]={0},min;

  • 0
    @ 2008-09-01 23:04:35

    MS这个可以状态压缩的~

  • 0
    @ 2008-08-22 12:36:53

    以石子为对象DP，定义状态f为跳到第i个石子左侧距离为j的位置需踩到的最少石子数。

    别忘了排序！

    还有，当距离>=s*(s-1)时，可以证明是一定能跳到的。

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    哈哈，第二次终于AC了！！！多亏了WJD的题解！！！(这里有2008hbnoi的OIer吗？哈哈)

    第一次只因为一点小错误，害我调了一个上午才发现，不爽啊！

  • 0
    @ 2008-08-20 22:03:24

    简单的DP不过学了一手，压缩n 用longint可恶，一味的节约空间以至于写了n次才AC

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

    唉！

    好烦！

    终于做了出来！

    想知道？

    不告诉你！

    哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈.........～！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

  • 0
    @ 2008-08-19 00:02:35

    难忘的题目啊!!!栽了N次本地Cena评测N次才AC 不容易啊！！！！

    压缩+DP

    编译通过...

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

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

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

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

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

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

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

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

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

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

过河

信息

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