题解 P1508 【Likecloud-吃、吃、吃】

feecle6418 · 2018-04-07 13:28:42 · 题解

其实这道题里面，f数组完全是多余的。我们可以直接在a数组里面迭代更新。 又因为输入是从上往下输入，而第i行的状态只跟第i-1行有关，所以完全可以边输入边更新。所以，我们可以大大的简化代码：

//by tianbu
//24ms,2.79MB
//代码：0.34KB C++
#include <iostream>
using namespace std;
int a[1005][1005];
int main() {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            a[i][j]+=max(a[i-1][j-1],max(a[i-1][j],a[i-1][j+1]));
        }
    }
    cout<<max(a[n][m/2],max(a[n][m/2+1],a[n][m/2+2]));
    return 0;
}