p1139.pas

www.vijos.cn上一些习题的参考源码

program p1139;
var
	m,n:longint;
	f:array[1..100,1..500] of longint;
	p,d:array[1..100,1..500] of longint;
	i,j:longint;
	a:array[1..50000] of longint;
	min,ll,ll1,rr,c,s:longint;
	
	
{function min3(a,b,c:longint):longint;
begin
	if(a<=b) and (a<=c) then exit(a)
	else if(b<=a) and (b<=c) then exit(b)
	else if (c<=a) and (c<=b) then exit(c);
end;

function min2(a,b:longint):longint;
begin
	if(a<=b) then min2:=a
	else min2:=b;
end;
}

begin
	readln(m,n);
	for i:=1 to m do begin
		for j:=1 to n do
			read(f[i,j]);
		readln;
	end;
	
	fillchar(d,sizeof(d),0);
	fillchar(p,sizeof(p),0);
	
	for j:=1 to n do begin
		d[1,j]:=f[1,j];
		p[1,j]:=-1;
	end;
					
	for i:=2 to m do begin
		for j:=1 to n do begin
			d[i,j]:=d[i-1,j];
			p[i,j]:=j;
		end;
		
		for j:=2 to n do
			if d[i,j]>d[i,j-1]+f[i,j-1] then begin
				d[i,j]:=d[i,j-1]+f[i,j-1];
				p[i,j]:=j-1;
			end;
		
		for j:=n-1 downto 1 do
			if d[i,j]>d[i,j+1]+f[i,j+1] then begin
				d[i,j]:=d[i,j+1]+f[i,j+1];
				p[i,j]:=j+1;
			end;
		
		for j:=1 to n do
			inc(d[i,j],f[i,j]);
	end;
	
	min:=d[m,1];
	s:=1;
	for j:=2 to n do begin
		if d[m,j]<min then begin
			min:=d[m,j];
			s:=j;
		end;
	end;
	
	fillchar(a,sizeof(a),0);
	ll:=m;
	rr:=s;
	ll1:=m;
	a[1]:=s;
	c:=1;
	while ll>1 do begin
		inc(c);
		if p[ll,s]=s then dec(ll1);
		if p[ll,s]=s+1 then inc(rr);
		if p[ll,s]=s-1 then dec(rr);
		ll:=ll1;
		s:=rr;
		a[c]:=s;
	end;
	
	for i:=c downto 1 do
		writeln(a[i]);
	readln;		
end.