// 问题描述】 // 小蓝有一个 n 行 m 列的矩阵 a[i][j] ,他想在矩阵中找出一个“口”字形状的区域,使得区域上的值的和最大。 // 具体讲,一个“口”字形状的区域可以由两个坐标 (x1, y1) 和 (x2, y2) 确定,满足: // 1 <= x1 < x2 <= n ; // 1 <= y1 < y2 <= m ; // x2 - x1 = y2 - y1 。 // 对应的区域由满足以下条件之一的点 (x, y) 构成: // x1 <= x <= x2,且 y = y1 ,对应“口”的左边一竖; // y1 <= y <= y2,且 x = x1 ,对应“口”的上面一横; // x1 <= x <= x2,且 y = y2 ,对应“口”的右边一竖; // y1 <= y <= y2,且 x = x2 ,对应“口”的下面一横。 // 请注意有些点满足以上条件的多个,例如左上角的点 (x1, y1) ,在计算时算为一个点。 // 区域上的值是指对应区域的所有点的值,即“口”字的框上的值,不含框内和框外的值。 // 【输入格式】 // 输入的第一行包含两个整数 n, m ,分别表示行数和列数。 // 接下来 n 行,每行包含 m 个整数,相邻数之间使用一个空格分隔,依次表示矩阵的每行每列的值,本部分的第 i 行第 j 列表示 a[i][j] 。 // 【输出格式】 // 输出一行包含一个整数,表示最大的和。 // 【样例输入】 // 5 6 // 1 -1 2 -2 3 -3 // -1 2 -2 3 -3 4 // 2 -2 3 -3 4 -4 // -2 3 -3 4 -4 5 // 3 -3 4 -4 5 -5 // 【样例输出】 // 4 // 【样例说明】 // 取 (x1, y1) = (1, 1) , (x2, y2) = (5, 5) 可得到最大值。 // 【评测用例规模与约定】 // 对于 30% 的评测用例,1 <= n, m <= 30 ,-1000 <= a[i][j] <= 1000 。 // 对于 60% 的评测用例,1 <= n, m <= 100 ,-1000 <= a[i][j] <= 1000 。 // 对于所有评测用例,1 <= n, m <= 300 ,-1000 <= a[i][j] <= 1000 。 #include #define MAX 301 int a[MAX][MAX]; int row_sum[MAX][MAX]; int col_sum[MAX][MAX]; int main() { int n, m; 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 <= n; i++) { row_sum[i][0] = 0; for (int j = 1; j <= m; j++) { row_sum[i][j] = row_sum[i][j - 1] + a[i][j]; } } for (int j = 1; j <= m; j++) { col_sum[j][0] = 0; for (int i = 1; i <= n; i++) { col_sum[j][i] = col_sum[j][i - 1] + a[i][j]; } } int max_sum = -1000000000; int k_max = (n - 1 < m - 1) ? (n - 1) : (m - 1); for (int k = 1; k <= k_max; k++) { for (int x1 = 1; x1 <= n - k; x1++) { int x2 = x1 + k; for (int y1 = 1; y1 <= m - k; y1++) { int y2 = y1 + k; int sum_left = col_sum[y1][x2] - col_sum[y1][x1 - 1]; int sum_top = row_sum[x1][y2] - row_sum[x1][y1 - 1]; int sum_right = col_sum[y2][x2] - col_sum[y2][x1 - 1]; int sum_bottom = row_sum[x2][y2] - row_sum[x2][y1 - 1]; int sum_corners = a[x1][y1] + a[x1][y2] + a[x2][y1] + a[x2][y2]; int total = sum_left + sum_top + sum_right + sum_bottom - sum_corners; if (total > max_sum) { max_sum = total; } } } } printf("%d\n", max_sum); return 0; }