n=1e3怎么区间DP
by GM_Joanna_ @ 2023-03-06 17:41:17
@[_Joanna_](/user/477865) 团队把题放区间里的
by luo_xiaoran @ 2023-03-27 11:37:46
```
#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:42:56
@[luo_xiaoran](/user/605945)
```
#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:53:00
@[huangmingyisunny1804](/user/966082) 感谢您的考古，已关注
by luo_xiaoran @ 2023-10-11 16:48:34