Hướng dẫn giải của Rectangles Perimeter


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

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.

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.