1 solutions

  • 0
    @ 2024-12-11 0:49:57

    C++ :

    /*
    	author :hzoi_ztx
    	title  :mine 
    	ALG    :dp 
    	comment:
    
    	[2014 10 20]
    */
    
    #include <cstdio>
    
    #define  maxn  1005
    
    int n , m , ans ;
    int sa[maxn][maxn] = {0} ;
    int sb[maxn][maxn] = {0} ;
    int f[maxn][maxn][2] = {0} ;
    
    int main() {
    	//#define  READ
    	#ifdef   READ
    		freopen("mine.in" ,"r",stdin ) ;
    		freopen("mine.out","w",stdout) ;
    	#endif
    	int i , j ;
    	scanf("%d%d", &n , &m ) ;
    	for (i = 1 ; i <= n ; i ++ )
    		for (j = 1 ; j <= m ; j ++ ) {
    			scanf("%d", &sa[i][j] ) ;
    			sa[i][j] += sa[i][j-1] ;
    		}
    	for (i = 1 ; i <= n ; i ++ )
    		for (j = 1 ; j <= m ; j ++ ) {
    			scanf("%d", &sb[i][j] ) ;
    			sb[i][j] += sb[i-1][j] ;
    		}
    	for (i = 1 ; i <= n ; i ++ ) {
    		for (j = 1 ; j <= m ; j ++ ) {
    			//东西 0
    			if (f[i-1][j][1] > f[i-1][j][0]) f[i][j][0] = f[i-1][j][1]+sa[i][j] ;
    			else f[i][j][0] = f[i-1][j][0]+sa[i][j] ;
    			//南北 1
    			if (f[i][j-1][1] > f[i][j-1][0]) f[i][j][1] = f[i][j-1][1]+sb[i][j] ;
    			else f[i][j][1] = f[i][j-1][0]+sb[i][j] ;
    		}
    	}
    /*	printf("nanbei :\n") ;
    	for (i = 1 ; i <= n ; i ++ ) {
    		printf("\n") ;
    		for (j = 1 ; j <= m ; j ++ ) printf("%d ",f[i][j][1]) ;
    	}
    	printf("\ndongxi : \n") ;
    	for (i = 1 ; i <= n ; i ++ ) {
    		printf("\n") ;
    		for (j = 1 ; j <= m ; j ++ ) printf("%d ",f[i][j][0]) ;
    	}
    */
    	if (f[n][m][1]>f[n][m][0]) f[n][m][0] = f[n][m][1] ;
    	printf("%d\n", f[n][m][0]);
    	#ifdef   READ
    		fclose(stdin ) ;
    		fclose(stdout) ;
    	#endif
    	return 0 ;
    }
    
    • 1

    Information

    ID
    768
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By