「BZOJ1177」[APIO2009]Oil

Description

Siruseri 政府决定将石油资源丰富的 Navalur 省的土地拍卖给私人承包商以 建立油井。被拍卖的整块土地为一个矩形区域,被划分为 M×NM\times N 个小块。 Siruseri 地质调查局有关于 Navalur 土地石油储量的估测数据。这些数据表示 为 M×NM\times N 个正整数,即对每一小块土地石油储量的估计值。 为了避免出现垄断,政府规定每一个承包商只能承包一个由 K×KK\times K 块相连的 土地构成的正方形区域。 AoE 石油联合公司由三个承包商组成,他们想选择三块互不相交的 K×KK\times K 的 区域使得总的收益最大。 例如,假设石油储量的估计值如下:

1
2
3
4
5
6
7
8
9
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=2K = 2, AoE 公司可以承包的区域的石油储量总和为 100100, 如果 K=3K = 3, AoE 公司可以承包的区域的石油储量总和为 208208。 AoE 公司雇佣你来写一个程序,帮助计算出他们可以承包的区域的石油储量之和的最大值。

Input

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

Output

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

Sample Input

1
2
3
4
5
6
7
8
9
10
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

1
208

HINT

数据保证 KMK\leq MKNK\leq N 并且至少有三个 K×KK\times K 的互不相交的正方形区域。
其 中 30%30\%的输入数据,M,N12M, N\leq 12
所有的输入数据, M,N×1500M, N\times 1500
每一小块土地的 石油储量的估计值是非负整数且×500\times 500

Solution

暴力枚举划分情况,算前缀最大和。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 2300;
int n, m, K;
int v[N][N];
int a[N][N], b[N][N], c[N][N], d[N][N];
int main() {
n = read(), m = read(), K = read();
if(K > max(n, m)) {
puts("0");
return 0;
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) {
scanf("%d",&v[i][j]);
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
v[i][j] += v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1];
for(int i = n; i >= K; --i)
for(int j = m; j >= K; --j)
v[i][j] -= v[i - K][j] + v[i][j - K] - v[i - K][j - K];
for(int i = K; i <= n; ++i)
for(int j = K; j <= m; ++j)
a[i][j] = max(max(a[i - 1][j], a[i][j - 1]), v[i][j]);
for(int i = K; i <= n; ++i)
for(int j = m - K + 1; j >= 1; --j)
b[i][j] = max(max(b[i - 1][j], b[i][j + 1]), v[i][j + K - 1]);
for(int i = n - K +1; i >= 1; --i)
for(int j = K; j <= m; ++j)
c[i][j] = max(max(c[i + 1][j], c[i][j - 1]), v[i + K - 1][j]);
/* for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j)
printf("%3d ", c[i][j]);
puts("");
}*/
for(int i = n - K + 1 ; i >= 1; --i)
for(int j = m - K + 1 ; j >= 1; --j)
d[i][j] = max(max(d[i + 1][j], d[i][j + 1]), v[i + K - 1][j + K - 1]);
int ans = 0;
for(int i = K; i <= n; ++i)
for(int j = K; j <= m; ++j) {
ans = max(ans, a[i][j] + b[i][j + 1] + c[i + 1][m]);
ans = max(ans, a[i][j] + b[n][j + 1] + c[i + 1][j]);
ans = max(ans, c[i][j] + a[i - 1][m] + d[i][j + 1]);
ans = max(ans, b[i][j] + a[n][j - 1] + d[i + 1][j]);
ans = max(ans, v[i][j] + a[n][j - K] + d[1][j + 1]);
ans = max(ans, v[i][j] + a[i - K][m] + d[i + 1][1]);
}
writeln(ans);
return 0;
}