描述

最近,Henry由于失恋(被某大牛甩掉！)心情很是郁闷.所以,他去了大牛家,寻求Michael大牛的帮助,让他尽快从失恋的痛苦中解脱出来.Michael大牛知道Henry是很爱钱的,所以他是费尽脑水,绞尽脑汁想出了一个有趣的游戏,帮助Henry.....

Michael把这个游戏取名为:Henry拣钱.为了帮助更多的人采用这种方法早日脱离失恋之苦,其实,这个游戏相当垃圾,目的就是为了满足Henry这种具有强烈好钱的心理的人.游戏是这样的:Michael首先找到了一块方形的土地,面积为m*n(米^2).然后他将土地划分为一平方米大小的方形小格.Michael在每个格子下都埋有钱(用非负数s表示,表示人民币的价值为s)和炸弹(用负数s表示,表示Henry挖出该方格下的东西会花掉s的钱去看病，医炸弹炸伤的伤口)...游戏的要求就是让Henry从一侧的中间列出发,按照下图的5种方式前进（前进最大宽度为5）,不能越出方格.他每到一个格子,必定要取走其下相应的东西.直到到达土地的另一侧,游戏结束.不用说也知道,Henry肯定想得到最多的人民币.所以他偷窥了,Michael埋钱的全过程,绘成了一张距阵图.由于他自己手动找会很麻烦,于是他就找到了学习编程的你.请给帮他找出,最大人民币价值.

拣钱路线规则(只有5个方向，如下图)：

H为Henry的出发点，每组数据的出发点都是最后一行的中间位置！(前方5个格子为当前可以到达的)

输入

第一行为m n.(n为奇数)，入口点在最后一行的中间接下来为m*n的数字距阵.共有m行,每行n个数字.数字间用空格隔开.代表该格子下是钱或炸弹.为了方便Henry清算,数字全是整数.

输出

一个数,为你所找出的最大人民币价值.

输入样例 1 

6 7 
16 4 3 12 6 0 3 
4 -5 6 7 0 0 2 
6 0 -1 -2 3 6 8 
5 3 4 0 0 -2 7 
-1 7 4 0 7 -5 6 
0 -1 3 4 12 4 2

输出样例 1

51

【数据范围】 N and M<=200. 结果都在longint范围内

题解：

AC Code

//
//  main.cpp
//  
//
//  Created by Edwin on 2019/3/8.
//  Copyright © 2019 Edwiv. All rights reserved.
//
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<a;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
const int maxn=200+10;
using namespace std;
ll Map[maxn][maxn];
int n,m;
ll ans=0;
ll maxx(ll a,ll b,ll c,ll d,ll e){
    return max(max(max(max(a,b),c),d),e);
}
int main(){
    sc2(n,m);
    mst(Map,-INF);
    FF(i,n)
    FF(j,m)
    scanf("%lld",&Map[i][j+2]);
    for(int i=1;i<n;++i){
        for(int j=2;j<m+2;++j){
            Map[i][j]=maxx(Map[i][j]+Map[i-1][j-2],Map[i][j]+Map[i-1][j-1],Map[i][j]+Map[i-1][j],Map[i][j]+Map[i-1][j+1],Map[i][j]+Map[i-1][j+2]);
        }
    }
    for(int i=m/2;i<=m/2+4;++i)
        ans=max(ans,Map[n-1][i]);
    printf("%lld\n",ans);
    return 0;
}