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

yangwenbin · 2019-09-21 10:40:54 · 题解

P1508 Likecloud-吃、吃、吃

这道题与dp的数塔问题比较相似

只是这个是有三条路线的

所以我们可以用数塔问题的思维来解题

首先李大水牛一开始在最后一行的中间的下方故： 我么需要的答案为最后一行中间三个的最大值（及 max(dp[n][m/2+1],max(dp[n][m/2],dp[n][m/2+2])); ）

其次是递归公式 这是一个二维dp，dp公式是该值是他的左上、正上、右上的dp结果的最大值+自身（及 dp[i][j]=max(max(dp[i-1][j],dp[i-1][j+1]),dp[i-1][j-1])+dp[i][j]; ）

CODE

#include <bits/stdc++.h>     //万能头文件
using namespace std;
int n,m,dp[250][250];       //多开50，避免RE
int main(void){
    memset(dp,0,sizeof(dp));  //统一初始化
    cin>>n>>m;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            cin>>dp[i][j];   //直接用dp数组存数值，节省空间（~~其实也省不了多少~~（强行划线））
        }
    }for (int i = 2; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            dp[i][j]=max(max(dp[i-1][j],dp[i-1][j+1]),dp[i-1][j-1])+dp[i][j];       //dp
        }
    }
    cout<<max(dp[n][m/2+1],max(dp[n][m/2],dp[n][m/2+2]));  //光荣输出，完结撒花
}