題目描述

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

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

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

輸入輸出格式

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

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

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

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

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

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

一個(gè)數(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

分析：就是一個(gè)數(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])

代碼：