@[IDNo1](/user/777131)
dfs 中 vis 数组前加 `!`
by IceKylin @ 2023-10-10 22:30:09
@[IceKylin](/user/719767) 输出 7，咋办捏
by IDNo1 @ 2023-10-10 22:35:50
@[IceKylin](/user/719767) 写一波记忆化，油炸炉，能不能再帮忙看看[捂脸]
```cpp
#include<bits/stdc++.h>
#define re register int
using namespace std;
inline int read()
{
re x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int N=1e3+5;
int n=read(),m=read();
int a[N][N];
bool vis[N][N];
int f[N][N];
int dx[3]={-1,1,0},dy[3]={0,0,1};
int xx,yy,ans=-INT_MAX;
inline void dfs(re x,re y,re fin)
{
if(f[x][y]>fin)
{
return ;
}
else
{
f[x][y]=fin;
}
if(x==n&&y==m)
{
return ;
}
for(re i=0;i<3;i++)
{
xx=x+dx[i],yy=y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m)
{
if(!vis[xx][yy])
{
vis[xx][yy]=1;
dfs(xx,yy,fin+a[xx][yy]);
vis[xx][yy]=0;
}
}
}
}
int main()
{
for(re i=1;i<=n;i++)
{
for(re j=1;j<=m;j++)
{
a[i][j]=read();
f[i][j]=-2147483647;
}
}
dfs(1,1,a[1][1]);
// for(re i=1;i<=n;i++)
// {
// for(re j=1;j<=m;j++)
// {
// cout<<f[i][j]<<" ";
// }
// cout<<endl;
// }
cout<<f[n][m];
return 0;
}
```
by IDNo1 @ 2023-10-10 22:41:10
```
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[1005][1005];
int dp[1005][1005][2];
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
memset(dp,-0x3f,sizeof(dp));
dp[0][1][0]=dp[0][1][1]=0;
for(int i=1;i<=n;i++){
dp[i][1][0]=dp[i][1][1]=dp[i-1][1][0]+a[i][1];
}
for(int j=2;j<=m;j++){
for(int i=1;i<=n;i++){
dp[i][j][0]=max(dp[i][j-1][0],max(dp[i][j-1][1],dp[i-1][j][0]))+a[i][j];
}
for(int i=n;i>=1;i--){
dp[i][j][1]=max(dp[i][j-1][0],max(dp[i][j-1][1],dp[i+1][j][1]))+a[i][j];
}
}
cout<<dp[n][m][0];
return 0;
}
```
by huangmingyisunny1804 @ 2023-10-11 15:38:44
@[IDNo1](/user/777131) 用dp
```
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[1005][1005];
int dp[1005][1005][2];
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
memset(dp,-0x3f,sizeof(dp));
dp[0][1][0]=dp[0][1][1]=0;
for(int i=1;i<=n;i++){
dp[i][1][0]=dp[i][1][1]=dp[i-1][1][0]+a[i][1];
}
for(int j=2;j<=m;j++){
for(int i=1;i<=n;i++){
dp[i][j][0]=max(dp[i][j-1][0],max(dp[i][j-1][1],dp[i-1][j][0]))+a[i][j];
}
for(int i=n;i>=1;i--){
dp[i][j][1]=max(dp[i][j-1][0],max(dp[i][j-1][1],dp[i+1][j][1]))+a[i][j];
}
}
cout<<dp[n][m][0];
return 0;
}
```
by huangmingyisunny1804 @ 2023-10-11 15:52:05