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:	1s
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

2014-09-24 06:01:12 longdt9x
nho. that! khoi? tao. f[0,j] vs f[i,0] tuong dung roi` ma` gui toan sai. >.< ai ngo` thieu' khoi tao hang cuoi'f[m+1,i] :v no cho ai<0 thi` f toan` = 0 :v mn can than nhe!

2014-09-24 06:01:12 longdt9x
Da AC!!

Last edit: 2014-09-24 06:02:01

2014-08-26 17:31:15 [ND] HI
vãi! dùng tất cả đều integer thì ko được gì, đổi lại longint với tăng giá trị maxm maxn lên lại AC ??????????

2014-08-15 07:15:46 ...
|a[i][j]| <=100; m,n<=100;
đặt biến Max = -10001; và mảng QHD -101 thì bị WA còn đặt cả 2 = 2^31 thì AC ?????

2014-08-11 16:08:39 Nguyễn Ðức Linh
0đ là sao hả m.n??

2014-08-10 14:32:58 ■■‡[ND] Bee Sociu■■‡
».«

2014-07-02 21:34:02 ♥*.*♥MTP♥*.*♥

Var
n,vt,m:Integer;
Res,S:Longint;
A:array[0..101,0..101] of Integer;
Function max(a,b:integer):integer;
begin
if a>b then max:=a
else max:=b;
end;
Procedure nhap;
var i,j:integer;
begin
Assign(input,'');
Reset(input);
Readln(n,m);
For i:=1 to N do
For j:=1 to M do
Read(a[i,j]);
For i:=0 to M+1 do
A[0,i]:=-maxint;
For i:=0 to N+1 do
A[i,0]:=-maxint;
For i:=0 to M+1 do
A[N+1,i]:=-maxint;
Close(input);
end;
Procedure xuat;
Begin
Assign(output,'');
Rewrite(output);
Write(RES);
Close(output);
End;
Procedure xuli;
var
i,j,maxx:Integer;
begin
Maxx:=-maxint;
S:=-maxlongint;
For i:=1 to N do
Begin
If Maxx<S then Maxx:=S;
VT:=i;
S:=A[vt,1];
For j:=1 to M-1 do
Begin
S:=S+max(a[vt,j+1],max(a[vt+1,j+1],a[vt-1,j+1]));
If max(a[vt,j+1],max(a[vt+1,j+1],a[vt-1,j+1]))=a[vt+1,j+1] then
vt:=vt+1;
If max(a[vt,j+1],max(a[vt+1,j+1],a[vt-1,j+1]))=a[vt-1,j+1] then
vt:=vt-1;
End;
End;
RES:=Maxx;
End;

BEGIN
Nhap;
Xuli;
Xuat;
END.

2014-07-02 21:33:54 ♥*.*♥MTP♥*.*♥
Sai cho nao`?

2014-06-03 14:16:55 .

Last edit: 2014-07-23 03:09:44

2014-05-19 14:32:35 [$Zeus$]
Mình Quy hoạch động và đã AC. KAKA

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

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

Input

Output

Example