題目描述

正處在某一特定時期之中的李大水牛由于消化系統(tǒng)比較發(fā)達，最近一直處在饑餓的狀態(tài)中。某日上課，正當(dāng)他餓得頭昏眼花之時，眼前突然閃現(xiàn)出了一個n*m(n and m<=200)的矩型的巨型大餐桌，而自己正處在這個大餐桌的一側(cè)的中點下邊。餐桌被劃分為了n*m個小方格，每一個方格中都有一個圓形的巨型大餐盤，上面盛滿了令李大水牛朝思暮想的食物。李大水牛已將餐桌上所有的食物按其所能提供的能量打了分（有些是負的，因為吃了要拉肚子），他決定從自己所處的位置吃到餐桌的另一側(cè)，但他吃東西有一個習(xí)慣——只吃自己前方或左前方或右前方的盤中的食物。

由于李大水牛已餓得不想動腦了，而他又想獲得最大的能量，因此，他將這個問題交給了你。

每組數(shù)據(jù)的出發(fā)點都是最后一行的中間位置的下方！

輸入輸出格式

輸入格式： [輸入數(shù)據(jù)：]

第一行為m n.(n為奇數(shù))，李大水牛一開始在最后一行的中間的下方

接下來為m*n的數(shù)字距陣.

共有m行,每行n個數(shù)字.數(shù)字間用空格隔開.代表該格子上的盤中的食物所能提供的能量.

數(shù)字全是整數(shù).

輸出格式： [輸出數(shù)據(jù)：]

一個數(shù),為你所找出的最大能量值.

輸入輸出樣例

輸入樣例#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： 41

分析：就是一個數(shù)字金字塔的變形。 轉(zhuǎn)移如下： f[i,j]=max(f[i-1,j-1],f[i-1,j],f[i-1,j+1]) 答案為 f[n+1,m div 2+1]=max(f[n,m div 2],f[n,m div 2+1],f[n,m div 2+2])

代碼：