Hướng dẫn giải của Đường đi có tổng lớn nhất

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,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.

Bình luận

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


  • 5
    ducquoc  đã bình luận lúc 14, Tháng 1, 2025, 13:48 ← chỉnh sửa

    Bài này mới nhìn có công thức tưởng dễ, thực tế lại khó (AC < 30%), chủ yếu tricky ở chỗ edge cases, max hàng dọc.

    (Giá trị cận có thể tới -100 x max(M, N)
    => Nên chọn giá trị min ban đầu <= -10000 , và có thể tính thêm -1 -2 cạnh biên. Lưu ý max tổng - chạm cột N - không nhất thiết lớn hơn các giá trị đơn trong table/matrix.)

    Example (Picture = 1000 words)
    qbmax<em>example</em>explanation.png

    Sample Java impl

    https://oj.vnoi.info/src/8178735 

    import java.io.*; import java.util.*;

// code mẫu của `ducquoc`

@SuppressWarnings("all") //https://oj.vnoi.info/problem/qbmax
class VoQbmax {
    public static void sol(PrintStream os) {
        QDS in = new QDS(); PrintWriter out = new PrintWriter(os);
        int M = in.nextInt(), N = in.nextInt(), A[][] = new int[M][N], dp[][] = new int[M + 2][N + 2], max = -1000_007;
        for (int i = 0; i <= M + 1; i++)
            for (int j = 0; j <= N + 1; j++) {
                if (i == 0 || j == 0 || i == M + 1 || j == N + 1) dp[i][j] = max;
                else dp[i][j] = A[i - 1][j - 1] = in.nextInt();
            }
        for (int j = 2; j <= N; j++)
            for (int i = 1; i <= M; i++) {
                dp[i][j] = A[i - 1][j - 1] + Math.max(dp[i - 1][j - 1], Math.max(dp[i][j - 1], dp[i + 1][j - 1]));
            }
        for (int i = 1; i <= M; i++) max = Math.max(max, dp[i][N]); //totalPath
        out.println(max); out.close(); in.close();
    }

    final public static void main(String[] args) throws Exception { //System.setOut(new PrintStream("O.out");
        System.setIn(new ByteArrayInputStream(("5 7\n9 -2 6 2 1 3 4\n0 -1 6 7 1 3 3\n8 -2 8 2 5 3 2\n" +
                "1 -1 6 2 1 6 1\n7 -2 6 2 1 3 7").getBytes())); //FileInputStream("I.inp"));
        sol(System.out);
    }
}
/** quick data Scanner */
class QDS {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1024); StringTokenizer st;
    public String next() { while (st == null || !st.hasMoreTokens()) { try { st = new StringTokenizer(
            br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); }
    public int nextInt() { return Integer.parseInt(next()); }
    public void close() { if (br != null) { try { br.close(); } catch (IOException e) { e.printStackTrace(); } } }
}