#include<bits/stdc++.h> using namespace std; #define ll long long int n,m; ll mat[1005][1005]; ll f[1005][1005]; ll sum[1005][1005]; int main() { //freopen("number.in","r",stdin); //freopen("number.out","w",stdout); cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>mat[i][j]; f[i][j] = -99999999; } } f[1][1] = mat[1][1]; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ sum[j][i] = sum[j-1][i]+mat[j][i]; } } for(int i=2;i<=n;i++){ f[i][1] = f[i-1][1]+mat[i][1]; } for(int i=2;i<=m;i++){ for(int j=1;j<=n;j++){ f[j][i] = f[j][i-1]+mat[j][i]; for(int k=1;k<=n;k++){ if(k==j)continue; else if(k<j){ f[j][i] = max(f[j][i],f[k][i-1]+sum[j][i]-sum[k-1][i]); } else{ f[j][i] = max(f[j][i],f[k][i-1]+sum[k][i]-sum[j-1][i]); } } } } cout<<f[n][m]<<endl; return 0; }
全部评论
(5) 回帖