題目描述

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

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

每組數據的出發點都是最后一行的中間位置的下方！

輸入輸出格式

輸入格式： [輸入數據：]

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

接下來為m*n的數字距陣.

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

數字全是整數.

輸出格式： [輸出數據：]

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

輸入輸出樣例

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

分析：就是一個數字金字塔的變形。 轉移如下： 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])

代碼：