Description
Crystal家的公司最近承包了一个大油田。整块油田为一个矩形区域，被划分为(n imes m)个小块。 Crystal亲自调查了每个小块的石油储备量。这些数据表示为(n imes m)个非负整数。但是Crystal现在心情不好，只想开采三个由(k imes k)块相连的土地构成的正方形区域。这些正方形区域必须互不重叠。 现在，Crystal想让你帮忙计算出她最多能开采出多少石油。
Input Format
第一行三个整数(n, m, k)。
接下来n行，每行m个整数，表示每个小块的储油量。
Output Format
一个整数，表示Crystal最多能开采出多少石油。
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
Hints
对于(100\%)的数据保证有解。
对于(40\%)的数据，保证(n, m, k le 12)。
对于(70\%)的数据，保证(n, m, k le 500)。
对于(100\%)的数据，保证(n, m, k le 1500)。
对于(100%)的数据，保证所有输入数据均为非负整数，且在(int)范围内。
这题就是APIO2009 Oil。
对于所有可能的合法解，(k imes k)的矩形分布只有六种情况，枚举求解即可。具体戳这里。
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef long long ll;
#define maxn (1510)
int N,M,K; ll sum[maxn][maxn],a[maxn][maxn],b[maxn][maxn],c[maxn][maxn],d[maxn][maxn],ans;
int main()
{
freopen("1585.in","r",stdin);
freopen("1585.out","w",stdout);
scanf("%d %d %d",&N,&M,&K);
for (int i = 1;i <= N;++i)
for (int j = 1;j <= M;++j)
a[i][j] = b[i][j] = c[i][j] = d[i][j] = -(1LL<<50);
for (int i = 1;i <= N;++i)
for (int j = 1;j <= M;++j)
scanf("%lld",sum[i]+j),sum[i][j] += sum[i][j-1];
for (int i = 1;i <= N;++i) for (int j = 1;j <= M;++j) sum[i][j] += sum[i-1][j];
for (int i = N;i >= K;--i) for (int j = M;j >= K;--j) sum[i][j] -= sum[i][j-K]+sum[i-K][j]-sum[i-K][j-K];
for (int i = K;i <= N;++i)
for (int j = K;j <= M;++j)
a[i][j] = max(sum[i][j],max(a[i-1][j],a[i][j-1]));
for (int i = K;i <= N;++i)
for (int j = M;j >= K;--j)
b[i][j] = max(sum[i][j],max(b[i-1][j],b[i][j+1]));
for (int i = N;i >= K;--i)
for (int j = K;j <= M;++j)
c[i][j] = max(sum[i][j],max(c[i+1][j],c[i][j-1]));
for (int i = N;i >= K;--i)
for (int j = M;j >= K;--j)
d[i][j] = max(sum[i][j],max(d[i+1][j],d[i][j+1]));
for (int i = K;i <= N-K;++i)
for (int j = K;j <= M-K;++j)
ans = max(ans,a[i][j]+b[i][j+K]+c[i+K][M]);
for (int i = K;i <= N-K;++i)
for (int j = (K<<1);j <= M;++j)
ans = max(ans,a[N][j-K]+b[i][j]+d[i+K][j]);
for (int i = K;i <= N-K;++i)
for (int j = K;j <= M-K;++j)
ans = max(ans,a[i][j]+b[N][j+K]+c[i+K][j]);
for (int i = (K << 1);i <= N;++i)
for (int j = K;j <= M-K;++j)
ans = max(ans,a[i-K][M]+c[i][j]+d[i][j+K]);
for (int i = K;i <= N;++i)
for (int j = (K<<1);j <= M-K;++j)
ans = max(ans,sum[i][j]+a[N][j-K]+b[N][j+K]);
for (int i = (K<<1);i <= N-K;++i)
for (int j = K;j <= M;++j)
ans = max(ans,sum[i][j]+a[i-K][M]+c[i+K][M]);
cout << ans;
fclose(stdin); fclose(stdout);
return 0;
}