QBMAX - Đường đi có tổng lớn nhất
Tác giả: happyboy99x
Ngôn ngữ: C++
#include <cstdio>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;
#define INF 1000000000
#define REP(i, n) for( int i = 0, _n = (n); i < _n; ++i )
#define F(j, i) (j >= 0 && j < n && i >= 0 && i < m ? f[j][i] : -INF)
typedef pair<int, int> ii;
int a[105][105], f[105][105];
int m, n;
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
scanf("%d%d", &m, &n);
REP(i, m) REP(j, n) scanf("%d", &a[i][j]);
REP(i,m) f[0][i] = a[i][0];
for(int j=1; j<n; ++j)
for(int i = 0; i < m; ++i)
f[j][i] = a[i][j] + max(F(j-1,i-1),max(F(j-1,i+1),F(j-1,i)));
int res = INT_MIN;
REP(i,m) res = max(res, f[n-1][i]);
printf( "%d\n", res );
return 0;
}