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

· · 题解

P1508题解

本蒟蒻第一次发题解，望管理员通过，还有请各位dalao勿喷..

其实这道题本身不难(然而本蒟蒻还是错了5次才AC)

楼下dalao已经说的足够清楚了，有两类思想可以解本题。

1、DFS加上剪枝(不加也可以，毕竟此题数据较小)

从起点，不断地向三个方向进行拓展，如果没有超出边界，取当前的最大值，即是否吃这个食物。最后在最上方进行搜索，找到最大值即可。

2、递推或者DP

因为李大牛只能向前，向左前方，向右前方(前进!!!)吃食物，为了让思路更清晰，我们便从上边往下边推。

状态转移方程：f[i][j]=f[i][j]+max(f[i-1][j],f[i-1][j-1],f[i-1][j+1])(1<=i<=m,1<=j<=n,f[i][j]表示在当李大牛在(i,j)时可以吃的食物的最大能量)

那么本蒟蒻用的是递推。

下面献上丑陋的代码...

------------------------华丽丽的分割线------------------------

#include<iostream>
#include<cstring>
using namespace std;
int a[210][210];
int f[210][210];//用来记录当前能得到的最大能量值
int max(int i,int j,int k)
{
    if ((i>=j)&&(i>=k)) return i;
    if ((j>=i)&&(j>=k)) return j;
    return k;
}//手打MAX函数，速度比STL快很多
int main()
{
    int m,n;
    cin>>m>>n;
    memset(a,-9999,sizeof(a));
    for (int i=1;i<=m;i++)
    for (int j=1;j<=n;j++) cin>>a[i][j];//得到每个食物的能量
    for (int i=1;i<=m;i++)
    for (int j=1;j<=n;j++) {
        f[i][j]=a[i][j];
        f[i][j]=f[i][j]+max(f[i-1][j],f[i-1][j-1],f[i-1][j+1]);}
        //状态转移方程
    cout<<max(f[m][n/2+1],f[m][n/2],f[m][n/2+2]);
    //由于最后可以有三个点可以到达中点，所以我们最后还有比较一边，取其最大值..
}

冗长的代码结束了..