3 solutions

  • 2
    @ 2024-11-19 17:03:32
    #include<bits/stdc++.h>
    typedef long long LL;
    using namespace std;
    const int N=10010;
    const LL min_ll = -1e18;
    int n, m;
    LL w[N][N];
    LL f[N][N][2];
    inline LL mx(LL p, LL q, LL r) {
    	return p > q ? (p > r ? p : r) : (q > r ? q : r);
    }
    inline LL dfs(int x, int y, int from) {
    	if (x < 1 || x > n || y < 1 || y > m) return min_ll;
    	if (f[x][y][from] != min_ll) return f[x][y][from];
    	if (from == 0) f[x][y][from] = mx(dfs(x + 1, y, 0), dfs(x, y - 1, 0), dfs(x, y - 1, 1)) + w[x][y];
    	else f[x][y][from] = mx(dfs(x - 1, y, 1), dfs(x, y - 1, 0), dfs(x, y - 1, 1)) + w[x][y];
    	return f[x][y][from];
    }
    int main(void) {
    	
    	scanf("%d %d", &n, &m);
    	for (int i = 1; i <= n; ++i)
    		for (int j = 1; j <= m; ++j) {
    			scanf("%lld", &w[i][j]);
    			f[i][j][0] = f[i][j][1] = min_ll;
    		}
    	f[1][1][0] = f[1][1][1] = w[1][1];
    	printf("%lld\n", dfs(n, m, 1));
    	
    	return 0;
    }
    
    • 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;
      }
      • -3
        @ 2024-11-19 17:07:37
        #include <stdio.h>
         typedef long long LL;
         const LL min\_ll = -1e18; 
        int n, m;
         LL w[1005][1005], f[1005][1005][2]; 
        inline LL mx(LL p, LL q, LL r) {return p > q ? (p > r ? p : r) : (q > r ? q : r);} inline LL dfs(int x, int y, int from) {     if (x < 1 || x > n || y < 1 || y > m) return min\_ll;     if (f[x][y][from] != min\_ll) return f[x][y][from];     if (from == 0) f[x][y][from] = mx(dfs(x + 1, y, 0), dfs(x, y - 1, 0), dfs(x, y - 1, 1)) + w[x][y];     else f[x][y][from] = mx(dfs(x - 1, y, 1), dfs(x, y - 1, 0), dfs(x, y - 1, 1)) + w[x][y];     return f[x][y][from]; } int main(void) { //	freopen("number.in", "r", stdin); freopen("number.out", "w", stdout); 	scanf("%d %d", &n, &m); 	for (int i = 1; i <= n; ++i) 		for (int j = 1; j <= m; ++j) { 			scanf("%lld", &w[i][j]); 			f[i][j][0] = f[i][j][1] = min\_ll; 		}     f[1][1][0] = f[1][1][1] = w[1][1]; 	printf("%lld\\n", dfs(n, m, 1)); 	return 0; }
        
        • 1

        Information

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