【BZOJ 1177】【APIO 2009】Oil

时间：2022-05-01 21:54:25

http://www.lydsy.com/JudgeOnline/problem.php?id=1177

前缀和优化，时间复杂度$O(nm)$

因为数据不全，快速读入会导致RE，切记！

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 1503;

int in() {

	int k = 0, fh = 1; char c = getchar();

	for(; c < '0' || c > '9'; c = getchar())

		if (c == '-') fh = -1;

	for(; c >= '0' && c <= '9'; c = getchar())

		k = (k << 3) + (k << 1) + c - '0';

	return k * fh;

}

int a[N][N], a1[N][N], a2[N][N], a3[N][N], a4[N][N], s[N][N];

int n, m, k, m1[N][N], m2[N][N], m3[N][N], m4[N][N], h[N], l[N];

void init1() {

	int S;

	for(int i = k; i <= n; ++i)

		for(int j = k; j <= m; ++j) {

			S = s[i][j] - s[i - k][j] - s[i][j - k] + s[i - k][j - k];

			a1[i - k + 1][j - k + 1] = S;

			a2[i - k + 1][j] = S;

			a3[i][j - k + 1] = S;

			a4[i][j] = S;

		}

}

void init2() {

	for(int i = n - k + 1; i >= 1; --i)

		for(int j = m - k + 1; j >= 1; --j)

			m1[i][j] = max(a1[i][j], max(m1[i + 1][j], m1[i][j + 1]));

	for(int i = n - k + 1; i >= 1; --i)

		for(int j = k; j <= m; ++j)

			m2[i][j] = max(a2[i][j], max(m2[i + 1][j], m2[i][j - 1]));

	for(int i = k; i <= n; ++i)

		for(int j = m - k + 1; j >= 1; --j)

			m3[i][j] = max(a3[i][j], max(m3[i - 1][j], m3[i][j + 1]));

	for(int i = k; i <= n; ++i)

		for(int j = k; j <= m; ++j)

			m4[i][j] = max(a4[i][j], max(m4[i - 1][j], m4[i][j - 1]));

}

int main() {

	scanf("%d%d%d", &n, &m, &k);

	for(int i = 1; i <= n; ++i)

		for(int j = 1; j <= m; ++j) {

			scanf("%d", &a[i][j]);

			s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i][j] - s[i - 1][j - 1];

		}

	init1();

	init2();

	int ans = 0, f1, f2, f3, f4;

	for(int i = k; i <= n - k; ++i)

		for(int j = k; j <= m - k; ++j) {

			f1 = m4[i][j] + m3[i][j + 1] + m1[i + 1][1];

			f2 = m3[i][j + 1] + m1[i + 1][j + 1] + m2[1][j];

			f3 = m2[i + 1][j] + m1[i + 1][j + 1] + m3[i][1];

			f4 = m4[i][j] + m2[i + 1][j] + m4[1][j + 1];

			ans = max(ans, f1);

			ans = max(ans, f2);

			ans = max(ans, f3);

			ans = max(ans, f4);

		}

	for(int i = k + 1; i <= n - (k << 1) + 1; ++i)

		for(int j = 1; j <= m - k + 1; ++j)

			h[i] = max(h[i], a1[i][j]);

	for(int i = k; i <= n - (k << 1); ++i)

		ans = max(ans, m3[i][1] + m1[i + k + 1][1] + h[i + 1]);

	for(int j = k + 1; j <= m - (k << 1) + 1; ++j)

		for(int i = 1; i <= n - k + 1; ++i)

			l[j] = max(l[j], a1[i][j]);

	for(int j = k; j <= m - (k << 1); ++j)

		ans = max(ans, m2[1][j] + m1[1][j + k + 1] + l[j + 1]);

	printf("%d\n", ans);

	return 0;

}

APIO的题目~

相关文章