HAF1 - Đua Xe

Tác giả: ladpro98

Ngôn ngữ: Pascal

program haf1;
uses    math;
const   maxn=1010;
        fi='';
var     a,f:array[0..maxn,0..maxn] of longint;
        m,n:longint;

procedure input;
var     inp:text;
        i,j:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n,m);
        for i:=1 to m do
        begin
                for j:=1 to n do
                read(inp,a[i,j]);
                readln(inp);
        end;
        close(inp);
end;

procedure dp;
var     i,j:longint;
begin
        for j:=1 to n do
        f[1,j]:=a[1,j];
        for i:=2 to m do
        begin
                for j:=1 to n do
                f[i,j]:=f[i-1,j]+a[i,j];
                for j:=2 to n do
                f[i,j]:=min(f[i,j],f[i,j-1]+a[i,j]);
                for j:=n-1 downto 1 do
                f[i,j]:=min(f[i,j],f[i,j+1]+a[i,j]);
        end;
end;

procedure output;
var     j:longint;
        res:longint;
begin
        res:=1234567890;
        for j:=1 to n do
        res:=min(res,f[m,j]);
        write(res);
end;

begin
        input;
        dp;
        output;
end.

Download