Solution - 「APIO2009」采油区域

这是本蒟蒻的第一篇紫题题解

题目传送门

这是一道比较考细节的题目

• 经读题可知要求一个矩阵三个边长为 \(k\) 子矩阵的和的最大值值，因为要求子矩阵，所以我们可以采用二维前缀和。
• 我们可以发现这个边长为 \(k\) 的子矩阵分布只会有 \(6\) 种情况（如下图）（本人就是因为没考虑到最后两种而卡了半天）
• 再灵活使用辅助数组即可

参考代码

#include 
using namespace std;
int m, n, k;
int a[2005][2005], sum[2005][2005];
int a1[2005][2005], b1[2005][2005], c1[2005][2005], d1[2005][2005], e[2005][2005], f[2005][2005];
int Sum(int x1, int y1, int x2, int y2) {
	return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]; 
}
int main() {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
		}
	}
	for (int i = k; i <= n; i++) {
		for (int j = k; j <= m; j++) {
			a1[i][j] = max(max(a1[i - 1][j], a1[i][j - 1]), Sum(i - k + 1, j - k + 1, i, j));
		}
	}
	//左上角最大
	for (int i = k; i <= n; i++) {
		for (int j = m - k + 1; j >= 1; j--) {
			b1[i][j] = max(max(b1[i - 1][j], b1[i][j + 1]), Sum(i - k + 1, j, i, j + k - 1));
		}
	} 
	//右上角最大
	for (int i = n - k + 1; i >= 1; i--) {
		for (int j = k; j <= m; j++) {
			c1[i][j] = max(max(c1[i + 1][j], c1[i][j - 1]), Sum(i, j - k + 1, i + k - 1, j));
		}
	} 
	//左下角最大
	for (int i = n - k + 1; i >= 1; i--) {
		for (int j = m - k + 1; j >= 1; j--) {
			d1[i][j] = max(max(d1[i + 1][j], d1[i][j + 1]), Sum(i, j, i + k - 1, j + k - 1));
		}
	} 
	//右下角最大
	for (int i = 1; i <= n - k + 1; i++) {
		for (int j = 1; j <= m - k + 1; j++) {
			e[i][i + k - 1] = max(e[i][i + k - 1], Sum(i, j, i + k - 1, j + k - 1));
		}
	}
	for (int n1 = k + 1; n1 <= n; n1++) {
		for (int i = 1, j = i + n1 - 1; j <= n; i++, j++) {
			e[i][j] = max(e[i + 1][j], e[i][j - 1]);
		}
	}
	//第 i ~ j行最大
	for (int i = 1; i <= m - k + 1; i++) {
		for (int j = 1; j <= n - k + 1; j++) {
			f[i][i + k - 1] = max(f[i][i + k - 1], Sum(j, i, j + k - 1, i + k - 1)); 
			
		}
	}
	for (int n1 = k + 1; n1 <= m; n1++) {
		for (int i = 1, j = i + n1 - 1; j <= m; i++, j++) {
			f[i][j] = max(f[i + 1][j], f[i][j - 1]);
		}
	}
	//第 i ~ j列最大
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ans = max(ans, e[i + 1][n] + a1[i][j] + b1[i][j + 1]);
			ans = max(ans, e[1][i] + c1[i + 1][j] + d1[i + 1][j + 1]);
			ans = max(ans, f[j + 1][m] + a1[i][j] + c1[i + 1][j]);
			ans = max(ans, f[1][j] + b1[i][j + 1] + d1[i + 1][j + 1]);
		}
	} 
	//一横一竖四种情况 
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			ans = max(ans, e[1][i] + e[i + 1][j] + e[j + 1][n]);
		}
	}
	//两个横着 
	for (int i = 1; i <= m; i++) {
		for (int j = i + 1; j <= m; j++) {
			ans = max(ans, f[1][i] + f[i + 1][j] + f[j + 1][m]);
		}
	}
	//两个竖着
	cout << ans; 
	return 0;
}