YC: Tìm con đường robot đi sao nhặt được số lượng vàng nhiều nhất.
DL vào: ROBOT.INP
- Dòng đầu chứa N và M (1<=N, M <=1000)
- N dòng sau, mỗi dòng có M số thể hiện số lượng vàng.
Kết quà: ROBOT.OUT, ghi tổng số lượng vàng nhặt được.
Ví dụ:
ROBOT.INP
|
ROBOT.OUT
|
3 4
1 1 1 1
5 2 2 100
9 4 2 1
|
111
|
Lời giải:
Phương pháp qui hoạch động đơn giản như sau:
F[i,j] = Max(F[i-1,j], F[i,j-1])+a[i,j], i:[1,N], j:[1,M]
Out: F[N,M]
Độ phức tạp O(NxM)
uses crt;
Trả lờiXóaconst fi='robot.inp'; tfo='robot.out';
var n,m,t: integer; Sum,Max:longint;
x: array[1..100] of integer;
a: array[0..100,0..100] of integer;
fo: text;
//------------------------------------------
Procedure Data;
var i,j: integer; f: text;
Begin
assign(f,fi); reset(f);
readln(f,n,m);
For i:=1 to n do
Begin
For j:=1 to m do
read(f,a[i,j]);
readln(f);
End;
Close(f);
End;
//-------------------------------------------
Procedure Print;
var i,u,v: integer;
Begin
Sum:=0;
u:=1; v:=1;
For i:=1 to (m+n-1) do
Begin
If x[i]=1 then {xuong}
Begin
u:=u; {dong}
v:=v+1; {hang}
Sum:=Sum+a[u,v];
End;
If x[i]=2 then {sang phai}
Begin
u:=u+1; {dong}
v:=v; {hang}
Sum:=Sum+a[u,v];
End;
End;
Sum:=Sum+a[1,1];
If Sum > Max then Max:=Sum;
End;
//------------------------------------------
Procedure Try(i: integer);
var j: integer;
Begin
For j:=1 to 2 do
Begin
x[i]:=j;
If i=(m+n-1) then print
else Try(i+1);
x[i]:=0;
End;
End;
//----------------------------------------
Begin
Max:=0;
clrscr;
Data;
Try(1);
assign(fo,tfo); rewrite(fo);
write(fo,max);
close(fo);
End.