洛谷 P1086 花生采摘

将植株按花生数从大到小排序，然后按排序后的顺序摘，每次摘前计算能否在摘后回到路边，如果能就将ans加上该植株花生数，如果不能就直接输出当前ans并退出。

var a:array[1..405,1..3] of integer;

i,j,x,y,m,n,k,n1,t1,ans,time:longint;

procedure sort(l,r:longint);

var i,j,m,t:longint;

begin

  i:=l;j:=r;

  m:=a[(l+r) div 2,1];

  repeat

    while a[i,1]>m do inc(i);

    while a[j,1]<m do dec(j);

    if (i<=j)  then

    begin

      t:=a[i,1];a[i,1]:=a[j,1];a[j,1]:=t;

      t:=a[i,2];a[i,2]:=a[j,2];a[j,2]:=t;

      t:=a[i,3];a[i,3]:=a[j,3];a[j,3]:=t;

      inc(i);dec(j);

    end;

    until i>j;

    if l<j then sort(l,j);

    if i<r then sort(i,r);

end;

begin

  readln(m,n,k);

  for i:=1 to m do

    for j:=1 to n do

    begin

      read(x);

      if x<>0

        then

        begin

          inc(n1);

          a[n1,1]:=x;

          a[n1,2]:=i;

          a[n1,3]:=j;

        end;

    end;

  sort(1,n1);

  x:=0;y:=a[1,3];

  for i:=1 to n1 do

  begin

    t1:=time+abs(a[i,2]-x)+abs(a[i,3]-y)+1;

    if t1+a[i,2]<=k

      then

      begin

        time:=t1;

        x:=a[i,2];

        y:=a[i,3];

        ans:=ans+a[i,1];

      end

      else

      begin

        writeln(ans);

        exit;

      end;

  end;

  writeln(ans);

end.

巴特西

洛谷 P1086 花生采摘

最新文章

热门文章