爆搜过不了,换个dp吧,至少记忆化
by ___PatrickChen___ @ 2023-10-02 11:44:58
@[___PatrickChen___](/user/608273) 谢谢
by zblueboil @ 2023-10-02 11:51:45
return 1<=x<=n&&1<=y<=m;
c++里没有a<=b<=c
by yangxiaojie @ 2023-10-02 12:01:59
额,对对对,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 chj121008 @ 2023-10-11 15:41:04