4 条题解

  • 2
    @ 2021-10-10 11:28:53
    #include <iostream>
    
    using namespace std;
    const int N = 60;
    int a[N][N];
    int dp[N][N][N][N];
    int main(){
    	int n, m;
    	cin >> n >> m;
    	for(int i = 1; i <= n; i++){
    		for(int j = 1; j <= m; j++){
    			cin >> a[i][j];
    		}
    	}
    	for(int i = 1; i <= n; i++){
    		for(int j = 1; j <= m; j++){
    			for(int x = 1; x <= n; x ++){
    				for(int y = 1; y <= m; y++){
    					int *t;
    					t = &dp[i][j][x][y];
    					*t = max(*t, dp[i-1][j][x][y-1]);
    					*t = max(*t, dp[i-1][j][x-1][y]);
    					*t = max(*t, dp[i][j-1][x-1][y]);
    					*t = max(*t, dp[i][j-1][x][y-1]);
    					*t += a[i][j] + a[x][y];
    					if(i == x && j == y)
    						*t -= a[x][y];
    				}
    			}
    		}
    	
    	}
    	cout << dp[n][m][n][m];
    } 
    

    信息

    ID
    186
    时间
    1000ms
    内存
    128MiB
    难度
    1
    标签
    递交数
    43
    已通过
    33
    上传者