OI

BZOJ 1177: [Apio2009]Oil

Description

采油区域 Siruseri政府决定将石油资源丰富的Navalur省的土地拍卖给私人承包商以建立油井。被拍卖的整块土地为一个矩形区域，被划分为M×N个小块。 Siruseri地质调查局有关于Navalur土地石油储量的估测数据。这些数据表示为M×N个非负整数，即对每一小块土地石油储量的估计值。 为了避免出现垄断，政府规定每一个承包商只能承包一个由K×K块相连的土地构成的正方形区域。 AoE石油联合公司由三个承包商组成，他们想选择三块互不相交的K×K的区域使得总的收益最大。 例如，假设石油储量的估计值如下： 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 8 8 8 8 8 1 1 1 1 8 8 8 8 8 1 1 1 1 8 8 8 8 8 1 1 1 1 1 1 1 8 8 8 1 1 1 1 1 1 1 1 8 8 8 1 1 1 1 1 1 9 9 9 1 1 1 1 1 1 9 9 9 如果K = 2, AoE公司可以承包的区域的石油储量总和为100, 如果K = 3, AoE公司可以承包的区域的石油储量总和为208。 AoE公司雇佣你来写一个程序，帮助计算出他们可以承包的区域的石油储量之和的最大值。

Input

输入第一行包含三个整数M, N, K，其中M和N是矩形区域的行数和列数，K是每一个承包商承包的正方形的大小（边长的块数）。接下来M行，每行有N个非负整数表示这一行每一小块土地的石油储量的估计值

Output

输出只包含一个整数，表示AoE公司可以承包的区域的石油储量之和的最大值。

Sample Input

9 9 3

1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1

1 8 8 8 8 8 1 1 1

1 8 8 8 8 8 1 1 1

1 8 8 8 8 8 1 1 1

1 1 1 1 8 8 8 1 1

1 1 1 1 1 1 8 8 8

1 1 1 1 1 1 9 9 9

1 1 1 1 1 1 9 9 9

Sample Output

208

Solution

分6种情况讨论一下即可。

上图片：

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2000;
int maxh[maxn][30], maxl[maxn][30], K[maxn], pre[maxn][maxn];
int lu[maxn][maxn], ld[maxn][maxn], ru[maxn][maxn], rd[maxn][maxn], mru[maxn][maxn], mld[maxn][maxn], mrd[maxn][maxn], mlu[maxn][maxn];
inline int sum(int x1, int y1, int x2, int y2) { return pre[x2][y2] - pre[x1][y2] - pre[x2][y1] + pre[x1][y1]; }
int qmaxh(int l, int r) {
	int len = r - l + 1;
	return max(maxh[l][K[len]], maxh[r-(1<<K[len])+1][K[len]]);
}
int qmaxl(int l, int r) {
	int len = r - l + 1;
	return max(maxl[l][K[len]], maxl[r-(1<<K[len])+1][K[len]]);
}
int n, m, kk, a[maxn][maxn];
int main() {
	scanf("%d%d%d", &n, &m, &kk);
	K[0] = -1;
	for (int i = 1; i <= n; ++i)
		K[i] = K[i>>1]+1;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			scanf("%d", &a[i][j]);
			pre[i][j] = pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];
		}
	for (int i = kk; i <= n; ++i)
		for (int j = kk; j <= m; ++j)
			ru[i][j - kk + 1] = ld[i - kk + 1][j] = rd[i - kk + 1][j - kk + 1] = lu[i][j] = sum(i - kk, j - kk, i, j);
	for (int i = kk; i <= n; ++i)
		for (int j = kk; j <= m; ++j)
			mlu[i][j] = max(max(mlu[i][j - 1], mlu[i - 1][j]), lu[i][j]);
	for (int i = kk; i <= n; ++i)
		for (int j = m - kk + 1; j; --j)
			mru[i][j] = max(max(mru[i - 1][j], mru[i][j + 1]), ru[i][j]);
	for (int i = n - kk + 1; i; --i)
		for (int j = m - kk + 1; j; --j)
			mrd[i][j] = max(max(mrd[i + 1][j], mrd[i][j + 1]), rd[i][j]);
	for (int i = n - kk + 1; i; --i)
		for (int j = kk; j <= m; ++j)
			mld[i][j] = max(max(mld[i][j - 1], mld[i + 1][j]), ld[i][j]);
	for (int i = kk; i <= n; ++i)
		for (int j = kk; j <= m; ++j)
			maxh[i][0] = max(maxh[i][0], lu[i][j]);
		//Wrong:maxh[i][0] = max(maxh[i][0], mlu[i][j]);
	for (int j = kk; j <= m; ++j)
		for (int i = kk; i <= n; ++i)
			maxl[j][0] = max(maxl[j][0], lu[i][j]);
		//Wrong:Tong Shang
	for (int k = 1; 1 << k <= n; ++k)
		for (int i = 1; i <= n; ++i)
			maxh[i][k] = max(maxh[i][k-1], maxh[i+(1<<(k-1))][k-1]);
	for (int k = 1; 1 << k <= m; ++k)
		for (int i = 1; i <= m; ++i)
			maxl[i][k] = max(maxl[i][k-1], maxl[i+(1<<(k-1))][k-1]);
	int ans = 0;
	for (int i = kk; i <= n - kk; ++i)
		for (int j = kk; j <= m - kk; ++j) {
			ans = max(ans, mlu[n][j] + mru[i][j+1] + mrd[i+1][j+1]); //Right
			ans = max(ans, mlu[i][m] + mld[i+1][j] + mrd[i+1][j+1]); //Down
			ans = max(ans, mru[n][j+1] + mlu[i][j] + mld[i+1][j]); //Left
			ans = max(ans, mru[i][j+1] + mlu[i][j] + mld[i+1][m]); //Up
		}
	for (int i = kk; i <= n; ++i)
		for (int j = i + kk; j <= n - kk; ++j)
			ans = max(ans, qmaxh(1, i) + qmaxh(i+kk, j) + qmaxh(j+kk, n));
		//Wrong: ans = max(ans, qmaxh(1, i) + qmaxh(i+1, j) + qmaxh(j+1, n));
	for (int i = kk; i <= m; ++i)
		for (int j = i + kk; j <= m - kk; ++j)
			ans = max(ans, qmaxl(1, i) + qmaxl(i+kk, j) + qmaxl(j+kk, m));
		//Wrong: Tong Shang
	printf("%d\n", ans);
}