3 solutions

  • 1
    @ 2025-8-11 14:37:21
    #include<bits/stdc++.h>
    #define ll long long
    #define fo(i,x,y) for(register int i=x;i<=y;++i)
    #define go(i,x,y) for(register int i=x;i>=y;--i)
    using namespace std;
    inline int read(){ int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') fh=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*fh; }
    const int N=1005;
    int a[N][N],n,m,S[N][N];
    ll dp[N][N],pre[N],suf[N];
    int main(){
    	n=read(),m=read();
    	fo(i,1,n)
    		fo(j,1,m) a[i][j]=read();
    	fo(j,1,m)
    		fo(i,1,n) S[j][i]=S[j][i-1]+a[i][j];//每一列的前缀和 
    	pre[0]=suf[n+1]=-1e17;
    	//由于转移的方式是从前一列直接到后一列
    	//因此第一列中除了第一行的元素其余的dp值均应赋为-inf,意为无法到达 
    	fill(dp[1]+2,dp[1]+1+n,-1e17);
    	dp[1][1]=a[1][1];
    	fo(i,2,m+1){//按列进行转移 
    		//预处理pre和suf数组 
    		fo(j,1,n) pre[j]=max(pre[j-1],dp[i-1][j]-S[i-1][j]);
    		go(j,n,1) suf[j]=max(suf[j+1],dp[i-1][j]+S[i-1][j-1]); 
    		fo(j,1,n) dp[i][j]=max(pre[j]+S[i-1][j],suf[j]-S[i-1][j-1])+a[j][i];
    	}
    	cout<<dp[m+1][n];
    	return 0;
    }

    Information

    ID
    77
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    7
    Tags
    # Submissions
    44
    Accepted
    10
    Uploaded By