```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define minn -1000000000
void read(int &x);
int dp[250][250],a[250][250];
int ny,nx;
int step[3]={-1,0,1};
int dfs(int y,int x)
{
if(y<=0 or y>ny or x<=0 or x>nx) return minn;
if(dp[y][x]!=minn) return dp[y][x];
int yy=y+1;
//cout<<"*";
for(int i=0;i<3;i++)
{
int xx=x+step[i];
if(yy>ny)
{
if(xx==nx/2 or xx==nx/2+1 or xx==nx/2+2) return dp[y][x]=a[y][x];
else return minn;
}
dp[y][x]=max(dfs(yy,xx)+a[y][x],dp[y][x]);
}
return dp[y][x];
}
int main()
{
read(ny),read(nx);
for(int i=1;i<=ny;i++) for(int j=1;j<=nx;j++) dp[i][j]=minn;
for(int i=1;i<=ny;i++) for(int j=1;j<=nx;j++) read(a[i][j]);
for(int i=1;i<=nx;i++) dfs(1,i);
int maxx=minn;
for(int j=1;j<=nx;j++) maxx=max(dp[1][j],maxx);
printf("%d",maxx);
return 0;
}
void read(int &x)
{
x=0;
int i=1;
char c=getchar();
while(c<'0' or c>'9')
{
if(c=='-') i=-1;
c=getchar();
}
while(c>='0' and c<='9')
{
x=x*10+c-'0';
c=getchar();
}
x*=i;
}
```
by 陌尘缘_怜 @ 2018-08-06 16:54:39
你这写的有点复杂,看看我的记忆化搜索
从上往下推的
```cpp
#include<cstdio>
const int INT_MIN=-1000000000;
const int INT_MAX=1000000000;
int n,m,map[201][201],f[201][201];
inline int max(int a,int b){
return a>b?a:b;
}
int dfs(int h,int l){
if(h<1||h>m||l<1||l>n) return INT_MIN;
if(h==1){
return map[h][l];
}
if(f[h][l]) return f[h][l];
return f[h][l]=max(map[h][l]+dfs(h-1,l),max(map[h][l]+dfs(h-1,l-1),map[h][l]+dfs(h-1,l+1)));
}
int main(){
scanf("%d %d",&m,&n);
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
scanf("%d",&map[i][j]);
}
}
printf("%d",max(dfs(m,(n+1)/2-1),max(dfs(m,(n+1)/2),dfs(m,(n+1)/2+1))));
}
```
by lingerleaf @ 2018-08-21 22:42:02