1 solutions
-
0
C++ :
#include<iostream> #include<cstdio> using namespace std; const int maxn=1005; int n,m,a[maxn][maxn]; long long dp[maxn][maxn][3]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); } } for(int i=1;i<=n;i++){ dp[i][1][2]=dp[i-1][1][2]+a[i][1]; } for(int j=2;j<=m;j++){ dp[1][j][0]=dp[1][j-1][2]+a[1][j]; for(int i=2;i<=n;i++){ dp[i][j][0]=max(dp[i][j-1][2],dp[i-1][j][0])+a[i][j]; } dp[n][j][1]=dp[n][j-1][2]+a[n][j]; for(int i=n-1;i>=1;i--){ dp[i][j][1]=max(dp[i][j-1][2],dp[i+1][j][1])+a[i][j]; } for(int i=1;i<=n;i++){ dp[i][j][2]=max(dp[i][j][0],dp[i][j][1]); } } cout<<dp[n][m][2]; return 0; }
- 1
Information
- ID
- 9125
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By