SPOJ.com - Problem QBMAX

Problem hidden

|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

Cho một bảng A kích thước m x n (1 <= m, n <= 100), trên đó ghi các số nguyên a_ij (|a_ij| <= 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

Example

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

Output:
41

Submit solution!

Được gửi lên bởi:	special_one
Ngày:	2008-06-12
Thời gian chạy:	0.131s
Giới hạn mã nguồn:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Ngôn ngữ cho phép:	Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments

2018-06-04 14:45:19
học sinh cô hương em trai anh mạnh 1 đấm ac :v

2018-04-11 11:55:16
đầu bìa lỗi kìa ~~!. dm mất bao lâu fig bug cua tui looix đầu bài. mảng giới hạn là n= m=102 nhá đau phải 100 đâu. sửa đi special one

2018-03-24 13:50:22
giúp với, toàn bị báo chạy quá thời gian, code mình đây:

public class Main {
public static void main(String[] args) {
Main main = new Main();
Scanner kb = new Scanner(System.in);
int m = kb.nextInt();
int n = kb.nextInt();
int[][] a = new int[m+2][n+2];

for (int j = 0; j <= n; j++)
{
a[0][j] = a[m+1][j] = -Integer.MAX_VALUE;
}

for (int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
a[i][j] = kb.nextInt();
}
}

for (int j = 2; j <= n; j++)
{
for (int i = 1; i <= m; i++)
{
a[i][j] += main.max(a[i-1][j-1], a[i][j-1], a[i+1][j-1]);
}
}

int result = -Integer.MAX_VALUE;

for (int i = 1; i <= m; i++)
{
result = Math.max(result, a[i][n]);
}
System.out.println(result);
}

public int max(int a, int b, int c)
{
int max = a;
if (b > max) max = b;
if (c > max) max = c;
return max;
}
}

2018-03-19 01:53:23
lay' link 9gb khong cuong` =))

2018-03-19 01:49:45

Last edit: 2018-03-19 01:51:57

2018-03-17 15:16:08
1 tát AC is real =) :V

2017-09-25 10:26:36
1 đấm AC :V

2017-09-10 19:18:25
Thuật toán:
https://vietcodes.github.io/code/73/

2017-08-21 09:20:50 Ðặng Minh Tiến
https://kienthuc24h.com/qbmax-spoj-duong-di-co-tong-lon-nhat/

Giải bài trực tuyến

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

Input

Output

Example