60pts求调!
查看原帖
60pts求调!
950927
_luo_gu楼主2024/8/21 15:13
#include <bits/stdc++.h>
using namespace std ;
int n , m , dp[1003][1003][5] , a[1003][1003] ;
int main(){
	scanf("%d%d" , &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 <= 3 ; i ++ ){
		for( int j = 1 ; j <= n ; j ++ ){
			for( int k = 1 ; k <= m ; k ++ ){
				dp[j][k][i] = -10000 ;
			}
		}
	}
	dp[1][1][1] = dp[1][1][2] = dp[1][1][3] = 0 ;
	//1从上到下      2从下到上   3从左到右 
	for( int j = 1 ; j <= m ; j ++ ){
		for( int i = 1 ; i <= n ; i ++ ){
			dp[i][j][1] = max(dp[max(1,i-1)][j][1] , dp[i][max(1,j-1)][3] ) + a[i][j] ; 
		}
		for( int i = n ; i >= 1 ; i -- ){
			dp[i][j][2] = max(dp[min(n,i+1)][j][2] , dp[i][max(1,j-1)][3] ) + a[i][j] ;
		}
		for( int i = 1 ; i <= n ; i ++ ){
			dp[i][j][3] = max(dp[i][j][1],dp[i][j][2] ) ;
		}
	}
	
	cout << dp[n][m][3] << endl;
	return 0 ;
}
2024/8/21 15:13
加载中...