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

``` //声明：本代码仅为蒟蒻编写，大佬勿喷 #include<cstdio> #include<cmath> #include<cstring>//在知道头文件的时候尽量一个一个写出来，防止占空间 using namespace std; long long a[210][210],f[210][210];//多开一些，因为初始牛在矩阵外，开小了会越界 int main() { int m,n; memset(f,-0x3f3f3f3f,sizeof(f));//有负数，清成小值 scanf("%d%d",&m,&n); for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { scanf("%lld",&a[i][j]); } }//至此为输入 f[m+1][n/2+1]=0;//牛站的地方(注意是在矩阵外，不要想成在最后一行的中间位置上,所以m+1） for(int i=m;i>=1;i--)//我是倒着循环，这样从最后的m层一直循环的第1层，答案即为f[1][1]到f[1][n]的值 { for(int j=1;j<=n;j++) { f[i][j]=fmax(fmax(f[i+1][j],f[i+1][j+1]),f[i+1][j-1])+a[i][j];//状态转移方程，即为三个方向 } } long long ans=-10000001;//有负值，开较小负数 for(int i=1;i<=n;i++) { if(f[1][i]>ans) ans=f[1][i]; } printf("%lld",ans);//输出 return 0; //注：本代码的long long为保险起见，因为题目并没有说每一个能量的范围 } ```