Bài 2. HSG Bảng B, Năm học 2018-2019
– Gọi S[i,j] là tổng giá trị lớn nhất các món quà robot thu được khi đi tới ô (i,j) là ô cột j ở hàng thứ i. Ta cần tính giá trị lớn nhất trong các S[h,i] với i=1,..,h.
Ta sẽ lưu dữ liệu đầu vào trong mảng A[i,j] và kết hợp luôn dữ liệu trong file THUQUA vào bằng cách đặt A[i,j]=-1 nếu ô(i,j) thu quà.
– Ta xác định hàm Quy hoạch động: Dễ thấy S[i,j] được tính thông qua
S[i-1,j-1] và S[i-1,j], tức là S[i,j] = max(S[i-1,j-1] , S[i-1,j])+A[i,j] với j>1, lưu ý S[i,j] =0 nếu A[i,j]=-1 (bị thu quà)
– Tính một số giá trị ban đầu(giá trị có thể tính được:
+ Giá trị đầu tiên:
S[1,1]=A[1,1] (S[1,1] =0 nếu A[i,j]=-1)
+ Tính các giá trị cột 1
S[i,1]=S[i-1,1]+ A[i,1] với i=2,..,h.
+ Tính các giá trị đường chéo.
S[i,i]:=S[i-1,i-1]+a[i,i]; với i=2,..,h
– Tính giá trị lặp hàm QHĐ
for i:=2 to h do
for j:=2 to h do
begin
S[i,j]:=S[i-1,j-1]+a[i,j];
if S[i-1,j-1]<S[i-1,j] then
S[i,j]:=S[i-1,j]+a[i,j];
end;
– Để đưa ra được đường đi ta phải lưu vết đường đi, gọi Truoc[i,j] là ô ngay trước ô(i,j) khi đi tới ô(i,j) cho S[i,j], dễ thấy Truoc[i,j] hoặc là ô (i-1,j-1) hoặc ô (i-1,j) nên ta chỉ cần lưu j-1 hoặc j là đủ.
{Code Pascal} {Bai 2 HSG Bang B nam hoc 2018-2019} uses crt; var a,s:array[1..501,1..501] of longint; truoc:array[1..500,1..500] of longint; h,n,vt:longint; {------Doc dl tam giac-----} procedure doc_tam_giac; var fi1:text; i,j:longint; begin assign(fi1,'tamgiac.inp'); reset(fi1); readln(fi1,h); while not eof(fi1) do begin for i:=1 to h do begin for j:=1 to i do read(fi1,a[i,j]); readln(fi1); end; end; end; {------Doc dl tu qua-----} procedure doc_thu_qua; var fi2:text; i,j,k:longint; begin assign(fi2,'thuqua.inp'); reset(fi2); while not eof(fi2) do begin readln(fi2,n); if n<>0 then begin for k:=1 to n do begin readln(fi2,i,j); a[i,j]:=-1; end; end; end; end; {------------Ham QHD-----------} procedure qhd; var i,j:longint; begin s[1,1]:=a[1,1]; truoc[1,1]:=0; if a[1,1]=-1 then s[1,1]:=0; {Tinh cac gia tri cot 1} for i:=2 to h do begin s[i,1]:=s[i-1,1]+a[i,1]; truoc[i,1]:=1; if a[i,1]=-1 then s[i,1]:=0; end; {Tinh cac gia tri duong cheo} for i:=2 to h do begin s[i,i]:=s[i-1,i-1]+a[i,i]; truoc[i,i]:=i-1; if a[i,i]=-1 then s[i,i]:=0; end; {Lap Ham QHD} for i:=2 to h do for j:=2 to h do begin if a[i,j]=-1 then s[i,j]:=0 else begin s[i,j]:=s[i-1,j-1]+a[i,j]; truoc[i,j]:=j-1; if s[i-1,j-1]<s[i-1,j] then begin s[i,j]:=s[i-1,j]+a[i,j]; truoc[i,j]:=j; end; end; end; vt:=1; for j:=2 to h do if s[h,vt]<s[h,j] then vt:=j; writeln('Gia tri Max=',s[h,vt]); end; {---------In dd thuan-------} procedure in_dd_thuan; var vet:array[1..500] of longint; i,j:longint; begin vet[h]:=vt; j:=truoc[h,vt]; for i:=h-1 downto 1 do begin vet[i]:=j; j:=truoc[i,j]; end; for i:=1 to h-1 do write(a[i,vet[i]],'(',i,',',vet[i],')->'); write(a[h,vt],'(',h,',',vt,')'); end; {--------In nguoc----} procedure in_dd_nguoc; var m,x:longint; begin write(a[h,vt],'(',h,',',vt,')'); m:=truoc[h,vt]; x:=h-1; while m>0 do begin write('->',a[x,m],'(',x,',',m,')'); m:=truoc[x,m]; x:=x-1; end; end; {------------Main--------------} begin clrscr; doc_tam_giac; doc_thu_qua; qhd; write('In duong di thuan:'); in_dd_thuan; writeln; write('In duong di nguoc:'); in_dd_nguoc; readln; end.