Đường đi có tổng lớn nhất
Xem dạng PDF
Gửi bài giải
Đ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
41
Bình luận
một bài quy hoạch động trên lưới khá dễ
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
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(); }
=3
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
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?!!
Khả năng cao edge cases là tính min/max bị sai, hoặc vượt giá trị biên.
hint:
Hope this helps,
bạn pk khởi tạo các giá trị ngoài ô thành 1 số âm cưc lớn ms đc
fix dc chx banj toi cung bi sai y het ma kbt suawr o dau
s
tloi
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
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
~ abs(A[i][j]) \leq 100 ~ thì tổng đường đi có thể xuống ~-100 \times M~ nhé.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.