Editorial for Rectangles Perimeter


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

var a:array[0..1,0..1] of longint;
    n,i,t,x,y,lx,ly:integer;

function max(a,b:longint):longint;
begin
     if a>=b then max:=a else max:=b;
end;

function c(a,b:longint):longint;
begin
     if a<=b then c:=-a
     else c:=a-2*b;
end;

begin
     fillchar(a,sizeof(a),0);
     readln(n);
     readln(x,y);
     a[1,0]:=x+y;
     a[1,1]:=x+y;
     lx:=x; ly:=y;
     for i:=2 to n do
     begin
          t:=i mod 2;
          readln(x,y);
          a[t,0]:=max(a[1-t,0]+c(x,lx),a[1-t,1]+c(x,ly))+x+y;
          a[t,1]:=max(a[1-t,0]+c(y,lx),a[1-t,1]+c(y,ly))+x+y;
          lx:=x; ly:=y;
     end;
     a[t,0]:=a[t,0]-x;
     a[t,1]:=a[t,1]-y;
     write(max(a[t,0],a[t,1]));
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<algorithm>
using namespace std;

#define N 1000
int f[N], g[N], a[N], b[N], n;
/* a[i]: chieu dai hinh chu nhat i
   b[i]: chieu rong hinh chu nhat i
   f[i]: xep hinh chu nhat thu i nam ngang
   g[i]: xep hinh chu nhat thu i dung dung
 */

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d%d", a+i, b+i);
        if(a[i] < b[i]) swap(a[i], b[i]);
    }
    f[0] = a[0]; g[0] = b[0];
    for(int i = 1; i < n; ++i) {
        f[i] = a[i] + max(abs(b[i] - b[i-1]) + f[i-1], abs(b[i] - a[i-1]) + g[i-1]);
        g[i] = b[i] + max(abs(a[i] - b[i-1]) + f[i-1], abs(a[i] - a[i-1]) + g[i-1]);
    }
    printf("%d\n", max(f[n-1], g[n-1]));
    return 0;
}

Code mẫu của ladpro98

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.

Code mẫu của RR

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=1011;
var
  f1,f2:text;
  n:longint;
  a,b:array[0..MAXN] of longint;
  d:array[0..MAXN,1..2] of longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure inp;
var
  i:longint;
begin
  read(f1,n);
  for i:=1 to n do
    read(f1,a[i],b[i]);
end;
procedure solve;
var
  i:longint;
begin
  d[1,1]:=b[1];
  d[1,2]:=a[1];
  for i:=2 to n do
    begin
      //Tinh 1
      d[i,1]:=abs(a[i]-a[i-1])+b[i]+d[i-1,1];
      d[i,1]:=max(d[i,1],abs(a[i]-b[i-1])+b[i]+d[i-1,2]);
      //Tinh 2
      d[i,2]:=abs(b[i]-a[i-1])+a[i]+d[i-1,1];
      d[i,2]:=max(d[i,2],abs(b[i]-b[i-1])+a[i]+d[i-1,2]);
    end;
end;
procedure ans;
begin
  writeln(f2,max(d[n,1],d[n,2]));
end;
begin
  openF;
  inp;
  solve;
  ans;
  closeF;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>

int TTD(int a)
{
    if(a<0) return -a;
    else return a;
}

int max(int a,int b)
{
    if(a>b) return a;
    else return b;
}

int main()
{
    int n,x[1001],y[1001];
    int A,B;
    scanf("%d",&n);
    for(int i = 1;i<=n;i++)
    {
        scanf("%d %d",&x[i],&y[i]);
        if(i==1)
        {
             A = x[i];
             B = y[i];
        }
        else 
        {
             int a = max(A+x[i]+TTD(y[i]-y[i-1]),B+x[i]+TTD(y[i]-x[i-1]));
             int b = max(B+y[i]+TTD(x[i]-x[i-1]),A+y[i]+TTD(x[i]-y[i-1]));
             A = a;
             B = b;
        }
    }
    printf("%d",max(A,B));
    //getch();
}

Code mẫu của ll931110

Program MMAXPER;
        Const
                input  = '';
                output = '';
        Var
                a,b: array[1..1000] of longint;
                  F: array[1..1000,0..1] of longint;
                  n: longint;

Procedure init;
          Var
                fi: text;
                 i: longint;
          Begin
                Assign(fi, input);
                        Reset(fi);

                        Readln(fi, n);
                        For i:= 1 to n do readln(fi, a[i], b[i]);
                Close(fi);
          End;

Function max(x,y: longint): longint;
         Begin
                If x < y then max:= y else max:= x;
         End;

Procedure optimize;
          Var
                i: longint;
          Begin
                F[1,0]:= a[1];             F[1,1]:= b[1];

                For i:= 2 to n do
                        Begin
                                F[i,0]:= max(F[i - 1,0] + abs(b[i] - b[i - 1]), F[i - 1,1] + abs(b[i] - a[i - 1]));
                                F[i,0]:= F[i,0] + a[i];

                                F[i,1]:= max(F[i - 1,0] + abs(a[i] - b[i - 1]), F[i - 1,1] + abs(a[i] - a[i - 1]));
                                F[i,1]:= F[i,1] + b[i];
                        End;
          End;

Procedure solve;
          Var
                fo: text;
          Begin
                Assign(fo, output);
                        Rewrite(fo);
                        Writeln(fo, max(F[n,0], F[n,1]));
                Close(fo);
          End;

Begin
        init;
        optimize;
        solve;
End.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.