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

Points: 0.05 (partial)

Time limit: 1.0s

Memory limit: 512M

Input: stdin

Output: stdout

Problem type

Allowed languages

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một bảng ~A~ kích thước ~m \times n~ ~(1 \le m~, ~n \le 100)~, trên đó ghi các số nguyên ~a_{ij}~ ~(|a_{ij}| \le 100)~. Một người xuất phát tại ô nào đó của cột ~1~, cần sang cột ~n~ (tại ô nào cũng được).

Quy tắc đi: Từ ô ~(i, j)~ chỉ được quyền sang một trong ~3~ ô ~(i, j + 1)~; ~(i - 1, j + 1)~; ~(i + 1, j + 1)~

Input

Dòng ~1~: Ghi hai số ~m~, ~n~ là số hàng và số cột của bảng.

~M~ dòng tiếp theo, dòng thứ ~i~ ghi đủ ~n~ số trên hàng ~i~ của bảng theo đúng thứ tự từ trái qua phải

Output

Gồm 1 dòng duy nhất ghi tổng lớn nhất tìm được

Sample Input

5 7
9 -2 6 2 1 3 4
0 -1 6 7 1 3 3
8 -2 8 2 5 3 2
1 -1 6 2 1 6 1
7 -2 6 2 1 3 7

Sample Output

Comments

Please read the guidelines before commenting.

-6

memme commented on Jan. 12, 2025, 3:07 p.m.

//LCS A4-K63 CTMK (r)

include <bits/stdc++.h>

using namespace std; typedef long long ll;

define f(i, a, n, c) for (ll i = a; i < n; i += c)

define fe(i, a, n, c) for (ll i = a; i <= n; i += c)

define append(a, n) a.push_back(n)

define del(a) a.pop_back()

define appended(a, n) a.emplace_back(n)

define vl vector<ll>

define vll vector

define vi vector<int>

define vii vector

define pll pair<ll, ll>

define pii pair<int, int>

define read freopen(".INP", "r", stdin);

define write freopen(".OUT", "w", stdout);

define sp iosbase::syncwith_stdio(0); cin.tie(0); cout.tie(0);

define llmin LLONG_MIN

define llmax LLONG_MAX

define imin INT_MIN

define imax INT_MAX

int main() { sp //read //write int m, n; cin >> m >> n;vii a(m, vi(n)); f(i, 0, m, 1) {f(j, 0, n, 1) {cin >> a[i][j];}}vii dp(m, vi(n, -1e9));f(i, 0, m, 1) {dp[i][0] = a[i][0];}f(j, 1, n, 1) {f(i, 0, m,1){dp[i][j] = dp[i][j - 1];if (i > 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1]);if (i < m - 1) dp[i][j] = max(dp[i][j], dp[i + 1][j - 1]);dp[i][j] += a[i][j]; } }int maxs = -1e9;f(i, 0, m, 1) {maxs = max(maxs, dp[i][n - 1]);} cout << maxs << "\n"; return 0; }

This comment is hidden due to too much negative feedback. Show it anyway.

0

HUNG2010 commented on Dec. 14, 2024, 3:36 a.m.

include<bits/stdc++.h>

define maxN 105

using namespace std; const int INF = 1e9;

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

void enter() { cin >> m >> n; for (int i =1; i <= m; i++){ for (int j =1; j <= n; j++) cin >> a[i][j]; } }

void solve(){ for (int i = 0; i <= m; i++) f[i][0] = 0; for (int i =0; i <= n; i++) f[0][i] = -INF; for (int i =0; i <= n; i++) f[m+1][i] = -INF; for (int j = 1; j <=n; j++){ for (int i =1; i <= m; i++) f[i][j] = max(max(f[i-1][j-1], f[i][j-1]), f[i+1][j-1]) + a[i][j];
} int res = -INF; for (int i = 1; i <=m; i++) res = max(res, f[i][n]); cout<<res; }

int main(){ enter(); solve(); }

0

nguyenduychan2024 commented on Oct. 23, 2024, 11:01 a.m. ← edited →

=3

-9

m1nkpk4nn commented on Aug. 6, 2024, 4:02 p.m.

de qua vay? co san ct ht roi

This comment is hidden due to too much negative feedback. Show it anyway.

0

melondepchai commented on June 13, 2024, 8:47 a.m.

4 test cuối xử lý như nào vậy mọi người, em sai 4 test cuối mà không biết fix sao?!!

0

ducquoc commented on Jan. 14, 2025, 1:52 p.m. ← edited →

Khả năng cao edge cases là tính min/max bị sai, hoặc vượt giá trị biên.

hint:

https://oj.vnoi.info/problem/qbmax/editorial#comment-8237

Hope this helps,

0

tranvandailong2k23 commented on Nov. 17, 2024, 8:50 a.m.

bạn pk khởi tạo các giá trị ngoài ô thành 1 số âm cưc lớn ms đc

0

DongDuc08 commented on Aug. 8, 2024, 8:38 a.m.

fix dc chx banj toi cung bi sai y het ma kbt suawr o dau

-4

HUY312132 commented on Jan. 19, 2024, 7:27 a.m. ← edited →

s

-3

Tloi_07 commented on Jan. 5, 2024, 1:29 a.m.

tloi

-8

Quangdpm commented on Dec. 23, 2023, 3:06 a.m.

khó

This comment is hidden due to too much negative feedback. Show it anyway.

-57

themluachon2008 commented on Oct. 8, 2023, 9:20 a.m.

xin downvote với mn

This comment is hidden due to too much negative feedback. Show it anyway.

-5

Hiiragi_Sergan commented on Sept. 1, 2023, 9:15 a.m.

Fix bug tùm lum luôn x__x

This comment is hidden due to too much negative feedback. Show it anyway.

-43

ksomg commented on Jan. 4, 2022, 4:10 p.m.

ảo ma

This comment is hidden due to too much negative feedback. Show it anyway.

-56

DoanTungLamKoCopyCode commented on Oct. 31, 2021, 1:57 p.m.

Bài này dùng Quy Hoạch Động

This comment is hidden due to too much negative feedback. Show it anyway.

1

mikamikaela commented on Aug. 3, 2021, 7:40 a.m.

Tác giả cho em hỏi có thực sự là (-100 <= A[i][j] <= 100) với mọi i, j không tác giả ơi.

Vì em để MIN là -(1e9+7) thì AC, còn để MIN là -107 thì tạch :V

18

ngfam commented on Aug. 3, 2021, 3:10 p.m.

~ abs(A[i][j]) \leq 100 ~ thì tổng đường đi có thể xuống ~-100 \times M~ nhé.

-13

mikamikaela commented on Aug. 5, 2021, 3:32 p.m.

em để MIN mà MIN của 1 cell cơ

This comment is hidden due to too much negative feedback. Show it anyway.

-8

jalsol commented on Aug. 5, 2021, 11:45 p.m.

1 cell trong mảng dp sẽ là tổng của cả đường đi, nên min của cell đó nên là min của tổng sẽ hợp lý hơn

This comment is hidden due to too much negative feedback. Show it anyway.

-199

dungp24 commented on May 30, 2021, 4:11 a.m. ← edited →

.

This comment is hidden due to too much negative feedback. Show it anyway.