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

2022-08-04 07:10:18
mọi người cho mình hỏi mình bị sai ở đâu với ạ, chạy input mẫu thì vẫn đc

#include<iostream>
using namespace std;

void nhap(int a[][100], int m, int n)
{
for (int i = 1; i <= m;i++)
{
for (int j = 1; j <= n;j++)
{
cin >> a[i][j];
}
}
}
int main()
{
int m, n;
cin >> m >> n;
int a[100][100];
int sum[100] = {0};

nhap(a, m, n);
for (int i = 1; i <= m;i++)
{
int cur_x = i;
int j = 1;
int cur_y = j;
sum[i] = a[cur_x][cur_y];
while (cur_y >= 1 && cur_y < n)
{
if (cur_x - 1 <= 0)
{
if (a[cur_x+1][cur_y + 1] >= a[cur_x][cur_y+1])
{
cur_x = cur_x + 1;
cur_y = cur_y + 1;
sum[i] += a[cur_x][cur_y];
}
else
{
cur_x = cur_x;
cur_y = cur_y+1;
sum[i] += a[cur_x][cur_y];
}
}

else if (cur_x + 1 > m)
{
if (a[cur_x-1][cur_y + 1] >= a[cur_x][cur_y+1])
{
cur_x = cur_x-1;
cur_y = cur_y + 1;
sum[i] += a[cur_x][cur_y];
}
else
{
cur_x = cur_x;
cur_y = cur_y+1;
sum[i] += a[cur_x][cur_y];
}
} // end else if

else
{
int max = a[cur_x - 1][cur_y + 1];
int temp = cur_x -1 ;
for (int i = cur_x - 1; i <= cur_x + 1; i++)
{
if (a[i][cur_y + 1] > max)
{
max = a[i][cur_y + 1];
temp = i;
}
}
cur_x = temp;
cur_y = cur_y + 1;
sum[i] += a[cur_x][cur_y];
}
} // end while
//cout << sum[i] << endl;
} // end for

int max = sum[1];
for (int i = 2; i <= m; i++)
{
if (sum[i] > max)
max = sum[i];
}
cout << max << endl;
}

2021-05-27 18:03:16
Tham khảo: https://vnspoj.github.io/problems/QBMAX

2020-12-03 09:10:47
phạm trần minh tuyên lê khiết quảng ngãi
gold medal giải chép code thế giới

2020-10-26 10:05:44
1 đấm ko AC :)

2020-07-09 19:43:55
TranTrungKienGoldIOI2021

2019-07-18 07:19:48
GHK 1 đấm AC

2019-02-09 04:57:08
khong biet tai sao dung test mau ma cu lam sai nhi

2018-07-22 18:29:05
ae

Last edit: 2018-09-08 15:59:45

2018-07-22 17:59:40
.

Last edit: 2018-07-22 18:29:28

2018-07-16 17:40:19
https://ideone.com/XGAi2L

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

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

Input

Output

Example