Editorial for Đường đi có tổng lớn nhất


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,b:array[0..101,1..100] of integer;
    n,m:byte;

procedure rf;
var i,j:byte;
begin
     readln(m,n);
     for i:=1 to m do
     begin
          for j:=1 to n do
              read(a[i,j]);
          readln;
     end;
end;

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

procedure pr;
var i,j:byte;
begin
     fillchar(b,sizeof(b),0);
     for j:=1 to n do
     begin
          b[0,j]:=-30000;
          b[n+1,j]:=b[0,j];
     end;
     for i:=1 to m do
         b[i,1]:=a[i,1];
     for j:=2 to n do
         for i:=1 to m do
             b[i,j]:=max(b[i-1,j-1],b[i,j-1],b[i+1,j-1])+a[i,j];
end;

procedure wf;
var  i:byte; max:integer;
begin
     max:=-32000;
     for i:=1 to m do
         if b[i,n]>max then max:=b[i,n];
     write(max);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

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

#define INF 1000000000
#define REP(i, n) for( int i = 0, _n = (n); i < _n; ++i )
#define F(j, i) (j >= 0 && j < n && i >= 0 && i < m ? f[j][i] : -INF)
typedef pair<int, int> ii;

int a[105][105], f[105][105];
int m, n;

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
#endif
    scanf("%d%d", &m, &n);
    REP(i, m) REP(j, n) scanf("%d", &a[i][j]);
    REP(i,m) f[0][i] = a[i][0];
    for(int j=1; j<n; ++j)
        for(int i = 0; i < m; ++i)
            f[j][i] = a[i][j] + max(F(j-1,i-1),max(F(j-1,i+1),F(j-1,i)));
    int res = INT_MIN;
    REP(i,m) res = max(res, f[n-1][i]);
    printf( "%d\n", res );
    return 0;
}

Code mẫu của ladpro98

program qbmax;
uses    math;
const   fi='';
var     a,tong:array[0..101,0..101] of longint;
        check:array[0..101,0..101] of boolean;
        res,m,n,i,minA:longint;
        inp:text;
procedure input;
var     i,j:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,m,n);
        for i:=1 to m do
        begin
                for j:=1 to n do
                begin
                        read(inp,a[i,j]);
                        minA:=min(a[i,j],minA);
                end;
                readln(inp);
        end;
        close(inp);
end;

function qhd(i,j:longint):longint;
var     temp:longint;
begin

        if check[i,j] then exit(tong[i,j]);

        temp:=qhd(i-1,j-1);
        temp:=max(temp,qhd(i,j-1));
        temp:=max(temp,qhd(i+1,j-1));

        tong[i,j]:=temp+a[i,j];
        check[i,j]:=true;
        exit(tong[i,j]);
end;

procedure init;
var     i:longint;
begin
        for i:=0 to n+1 do begin
                tong[0,i]:=low(integer);
                check[0,i]:=true;
                tong[m+1,i]:=low(integer);
                check[m+1,i]:=true;
        end;

        for i:=1 to m do
        begin
                tong[i,0]:=low(integer);
                check[i,0]:=true;
                tong[i,n+1]:=low(integer);
                check[i,n+1]:=true;
        end;
        for i:=1 to m do
        begin
                tong[i,1]:=a[i,1];
                check[i,1]:=true;
        end;

end;

begin
        input;
        init;
        res:=low(longint);
        for i:=1 to m do
                res:=max(res,qhd(i,n));
        write(res);
end.

Code mẫu của RR

{$R+,Q+}
uses math;
var
  a,f:array[-1..111,-1..111] of longint;
  m,n,i,j:longint;
begin
  read(m,n);
  for i:=1 to m do
  for j:=1 to n do
    read(a[i,j]);


  fillchar(f,sizeof(f),$80);
  for i:=1 to m do
    f[i,1]:=a[i,1];

  for j:=2 to n do
    for i:=1 to m do
      f[i,j]:=max(max(f[i-1,j-1],f[i,j-1]),f[i+1,j-1])+a[i,j];

  j:=-1000111000;
  for i:=1 to m do
    j:=max(j,f[i,n]);
  writeln(j);
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
main()
{
int n,m,a[102][102],b[102][102],max,max1=-10000;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
  for(int j=1;j<=m;j++)
    scanf("%d",&a[i][j]);
for(int j=1;j<=m;j++)
  { b[0][j]=-10000; b[n+1][j]=-10000; }
for(int i=1;i<=n;i++)
  b[i][1]=a[i][1];
for(int j=2;j<=m;j++)
  for(int i=1;i<=n;i++)
    {
    if(b[i-1][j-1]>b[i][j-1])
       max=b[i-1][j-1];
    else max=b[i][j-1];
    if(max<b[i+1][j-1])
      max=b[i+1][j-1];
    b[i][j]=max+a[i][j];
    }
for(int i=1;i<=n;i++)
  if(b[i][m]>max1)
    max1=b[i][m];
printf("%d",max1);
//getch();
}

Code mẫu của ll931110

Program QBMAX;
        Const
                input  = '';
                output = '';
        Var
                  A,B: array[0..200,0..200] of longint;
                  m,n: longint;

Procedure init;
          Var
                f: text;
                i,j: longint;
          Begin
                Assign(f, input);
                        Reset(f);
                        Readln(f, m, n);
                                For i:= 1 to m do
                                        For j:= 1 to n do read(f, A[i,j]);
                Close(f);
          End;

Procedure optimize;
          Var
                      f: text;
                  i,j,s: longint;
          Begin
                For i:= 0 to n do
                        Begin
                                B[0,i]:= -1000000000;
                                B[m + 1,i]:= -1000000000;
                        End;
                For i:= 1 to m do B[i,1]:= A[i,1];

                For j:= 2 to n do
                    For i:= 1 to m do
                        Begin
                                B[i,j]:= B[i - 1,j - 1];
                                If B[i,j] < B[i,j - 1] then B[i,j]:= B[i,j - 1];
                                If B[i,j] < B[i + 1,j - 1] then B[i,j]:= B[i + 1,j - 1];
                                B[i,j]:= B[i,j] + A[i,j];
                        End;

                s:= B[1,n];
                For i:= 2 to m do if s < B[i,n] then s:= B[i,n];

                Assign(f, output);
                        Rewrite(f);
                        Writeln(f, s);
                Close(f);
          End;

Begin
        init;
        optimize;
End.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.