BZOJ 1668 [Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富

题目大意

一个方格图，每个点都有权值，只能向右，向右下，向右上走，问从(1,1)走到(r,c)获得的最大权值。

SBDP

设 $F_{i,j}$ 表示到点 $(i,j)$ 获得的最大权值，于是就有$F_{i,j} = F_{i-1,j-1} + F_{i,j-1} + F_{i+1,j-1}$

之后注意边界条件，递推顺序，初值等等一系列东西，之后就可以了qwq

有生之年系列qwq

#include <cstdio>
#include <algorithm>
using namespace std;
int r,c,s[110][110],f[110][110];
int main()
{
    scanf("%d%d",&r,&c);
    for(int i=1;i<=r;++i)
        for(int j=1;j<=c;++j) scanf("%d",&s[i][j]);
    f[1][1]=s[1][1];
    for(int i=1;i<c;++i)
        for(int j=1;j<=r;++j)
        {
            if(!f[j][i]) continue;
            if(j-1>0) f[j-1][i+1]=max(f[j-1][i+1],f[j][i]+s[j-1][i+1]);
            f[j][i+1]=max(f[j][i+1],f[j][i]+s[j][i+1]);
            if(j+1<=r) f[j+1][i+1]=max(f[j+1][i+1],f[j][i]+s[j+1][i+1]);
        }
    printf("%d\n",f[r][c]);
    return 0;
}