.
2023-10-16 16:54:31
发布于:广东
25阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
const long long min_ll=-1e18;
int n,m;
long long w[1010][1010];
long long f[1010][1010][2];
inline long long mx(long long p,long long q,long long r)
{
return p>q?(p>r?p:r):(q>r?q:r);
}
long long dfs(int x, int y, int from)
{
if(x<1||x>n||y<1||y>m) return min_ll;
if(f[x][y][from]!=min_ll) return f[x][y][from];
if(from==0) f[x][y][from]=mx(dfs(x+1,y,0),dfs(x,y-1,0),dfs(x,y-1,1))+w[x][y];
else f[x][y][from]=mx(dfs(x-1,y,1),dfs(x,y-1,0),dfs(x,y-1,1))+w[x][y];
return f[x][y][from];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
cin>>w[i][j];
f[i][j][0]=f[i][j][1]=min_ll;
}
}
f[1][1][0]=f[1][1][1]=w[1][1];
cout<<dfs(n,m,1)<<endl;
return 0;
}
这里空空如也
有帮助,赞一个