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

Điểm: 0,05 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

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

Bình luận

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

-16

THPTHD_Hieu đã bình luận lúc 15, Tháng 5, 2025, 6:48

hạo lam hạo lam

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-8

RussVN123 đã bình luận lúc 21, Tháng 5, 2025, 5:39

Dangrangto > Hiếu thứ 2

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-8

anle82917 đã bình luận lúc 21, Tháng 5, 2025, 5:21

Hiếu chiến phết . Gà chiến số 1 HD

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-4

daotrungkiena1k46 đã bình luận lúc 20, Tháng 4, 2025, 13:19

một bài quy hoạch động trên lưới khá dễ

-8

memme đã bình luận lúc 12, Tháng 1, 2025, 15:07

//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; }

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-5

HUNG2010 đã bình luận lúc 14, Tháng 12, 2024, 3:36

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(); }

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

0

nguyenduychan2024 đã bình luận lúc 23, Tháng 10, 2024, 11:01 ← chỉnh sửa →

=3

-10

m1nkpk4nn đã bình luận lúc 6, Tháng 8, 2024, 16:02 ← chỉnh sửa →

.

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

0

melondepchai đã bình luận lúc 13, Tháng 6, 2024, 8:47

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?!!

5

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

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 đã bình luận lúc 17, Tháng 11, 2024, 8:50

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 đã bình luận lúc 8, Tháng 8, 2024, 8:38

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

-5

HUY312132 đã bình luận lúc 19, Tháng 1, 2024, 7:27 ← chỉnh sửa →

s

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-4

Tloi_07 đã bình luận lúc 5, Tháng 1, 2024, 1:29

tloi

-8

Quangdpm đã bình luận lúc 23, Tháng 12, 2023, 3:06

khó

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-65

themluachon2008 đã bình luận lúc 8, Tháng 10, 2023, 9:20

xin downvote với mn

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-5

Hiiragi_Sergan đã bình luận lúc 1, Tháng 9, 2023, 9:15

Fix bug tùm lum luôn x__x

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-43

ksomg đã bình luận lúc 4, Tháng 1, 2022, 16:10

ảo ma

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-61

DoanTungLamKoCopyCode đã bình luận lúc 31, Tháng 10, 2021, 13:57

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

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-1

mikamikaela đã bình luận lúc 3, Tháng 8, 2021, 7:40

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 đã bình luận lúc 3, Tháng 8, 2021, 15:10

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

-13

mikamikaela đã bình luận lúc 5, Tháng 8, 2021, 15:32

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

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-6

jalsol đã bình luận lúc 5, Tháng 8, 2021, 23:45

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

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-213

dungp24 đã bình luận lúc 30, Tháng 5, 2021, 4:11 ← chỉnh sửa →

.

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.