MMAXPER - Rectangles Perimeter

Tác giả: ladpro98

Ngôn ngữ: Pascal

program mmaxper;
uses    math;
type    rect = record
        dai,rong: longint;
        end;
const   ngang = 1;
        doc = 2;
        fi='';
        maxN = 1000;

var     f:array[1..maxN,ngang..doc] of longint;
        a:array[1..maxN] of rect;
        n:longint;
procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        readln(inp,a[i].dai,a[i].rong);
        close(inp);
end;

procedure dp;
var     i,j:longint;
begin
        for i:=2 to n do
        for j:=ngang to doc do
        begin

                if j=ngang then
                f[i,j]:=a[i].dai +
                      max(f[i-1,ngang]+abs(a[i].rong-a[i-1].rong),
                          f[i-1,doc]+abs(a[i].rong-a[i-1].dai))
                else
                f[i,j]:=a[i].rong +
                      max(f[i-1,doc]+abs(a[i].dai-a[i-1].dai),
                          f[i-1,ngang]+abs(a[i].dai-a[i-1].rong));
        end;
end;

procedure init;
begin
        f[1,doc]:=a[1].rong;
        f[1,ngang]:=a[1].dai;
end;

procedure output;
begin
        write(max(f[n,doc],f[n,ngang]));
end;

begin
        input;
        init;
        dp;
        output;
end.

Download