算法训练 采油区域
时间限制:2.0s 内存限制:512.0MB
提交此题 查看参考代码
采油区域 Siruseri*决定将石油资源丰富的Navalur省的土地拍卖给私人承包商以建立油井。被拍卖的整块土地为一个矩形区域,被划分为M×N个小块。
Siruseri地质调查局有关于Navalur土地石油储量的估测数据。这些数据表示为M×N个非负整数,即对每一小块土地石油储量的估计值。
为了避免出现垄断,*规定每一个承包商只能承包一个由K×K块相连的土地构成的正方形区域。
AoE石油联合公司由三个承包商组成,他们想选择三块互不相交的K×K的区域使得总的收益最大。
例如,假设石油储量的估计值如下:
如果K = 2, AoE公司可以承包的区域的石油储量总和为100, 如果K = 3, AoE公司可以承包的区域的石油储量总和为208。
AoE公司雇佣你来写一个程序,帮助计算出他们可以承包的区域的石油储量之和的最大值。
输入格式
输入第一行包含三个整数M, N, K,其中M和N是矩形区域的行数和列数,K是每一个承包商承包的正方形的大小(边长的块数)。接下来M行,每行有N个非负整数表示这一行每一小块土地的石油储量的估计值。
输出格式
输出只包含一个整数,表示AoE公司可以承包的区域的石油储量之和的最大值。
数据规模和约定
数据保证K≤M且K≤N并且至少有三个K×K的互不相交的正方形区域。其中30%的输入数据,M, N≤ 12。所有的输入数据, M, N≤ 1500。每一小块土地的石油储量的估计值是非负整数且≤ 500。
样例输入
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
样例输出
208
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class 采油区域 {
static int map[][];
static int sum[][];
static int kk[][];
static int leftup[][];
static int rightup[][];
static int leftdown[][];
static int rightdown[][];
static int max(int a, int b) {
return a>b?a:b;
}
static void print(int arr[][]) {
for(int i=0;i<arr.length;i++) {
for(int j=0;j<arr[i].length;j++) {
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
System.out.println();
}
public static void main(String args[]) throws IOException {
int M,N,K;
//Scanner in = new Scanner(System.in);
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//录入数据
String cs[] = br.readLine().split(" ");
M=Integer.valueOf(cs[0]);
N=Integer.valueOf(cs[1]);
K=Integer.valueOf(cs[2]);
//M=in.nextInt();
//N=in.nextInt();
//K=in.nextInt();
int m = M-K+1;
int n = N-K+1;
map = new int[M+1][N+1];
for(int i=1;i<=M;i++) {
cs = br.readLine().split(" ");
for(int j=1;j<=N;j++) {
//map[i][j]=in.nextInt();
map[i][j]=Integer.valueOf(cs[j-1]);
}
}
//用前缀和计算 sum
sum = new int[M+1][N+1];
for(int i=1;i<=M;i++) {
for(int j=1;j<=N;j++) {
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+map[i][j];
}
}
//用前缀和计算kk
kk = new int[m][n];
for(int i=K;i<=M;i++) {
for(int j=K;j<=N;j++) {
kk[i-K][j-K]=sum[i][j]-sum[i-K][j]-sum[i][j-K]+sum[i-K][j-K];
}
}
//计算四个方向的max
leftup = new int[m][n];
rightup = new int[m][n];
leftdown = new int[m][n];
rightdown = new int[m][n];
leftup[0][0]=kk[0][0];
for(int i=1;i<m;i++)
leftup[i][0]=max(kk[i][0], leftup[i-1][0]);
for(int j=1;j<n;j++)
leftup[0][j]=max(kk[0][j], leftup[0][j-1]);
for(int i=1;i<m;i++) {
for(int j=1;j<n;j++) {
leftup[i][j]=max(kk[i][j], max(leftup[i-1][j], leftup[i][j-1]));
}
}
rightup[0][n-1]=kk[0][n-1];
for(int i=1;i<m;i++)
rightup[i][n-1]=max(kk[i][n-1], rightup[i-1][n-1]);
for(int j=n-2;j>=0;j--)
rightup[0][j]=max(kk[0][j], rightup[0][j+1]);
for(int i=1;i<m;i++) {
for(int j=n-2;j>=0;j--) {
rightup[i][j]=max(kk[i][j], max(rightup[i-1][j], rightup[i][j+1]));
}
}
leftdown[m-1][0]=kk[m-1][0];
for(int i=m-2;i>=0;i--)
leftdown[i][0]=max(kk[i][0], leftdown[i+1][0]);
for(int j=1;j<n;j++)
leftdown[m-1][j]=max(kk[m-1][j], leftdown[m-1][j-1]);
for(int i=m-2;i>=0;i--) {
for(int j=1;j<n;j++) {
leftdown[i][j]=max(kk[i][j], max(leftdown[i][j-1], leftdown[i+1][j]));
}
}
rightdown[m-1][n-1]=kk[m-1][n-1];
for(int i=m-2;i>=0;i--)
rightdown[i][n-1]=max(kk[i][n-1], rightdown[i+1][n-1]);
for(int j=n-2;j>=0;j--)
rightdown[m-1][j]=max(kk[m-1][j], rightdown[m-1][j+1]);
for(int i=m-2;i>=0;i--) {
for(int j=n-2;j>=0;j--) {
rightdown[i][j]=max(kk[i][j], max(rightdown[i+1][j], rightdown[i][j+1]));
}
}
//计算六种情况
int ans=0;
//一
for(int j=0;j<n-2*K;j++) {
for(int i=0;i<m;i++) {
ans = max(ans, leftup[m-1][j]+kk[i][j+K]+rightup[m-1][j+K+K]);
}
}
//|
for(int i=0;i<m-2*K;i++) {
for(int j=0;j<n;j++) {
ans = max(ans, leftup[i][n-1]+kk[i+K][j]+leftdown[i+K+K][n-1]);
}
}
//左
for(int i=0;i<m-K;i++) {
for(int j=0;j<n-K;j++) {
ans = max(ans, leftup[m-1][j]+rightup[i][j+K]+rightdown[i+K][j+K]);
}
}
//右
for(int i=0;i<m-K;i++) {
for(int j=n-1;j-K>0;j--) {
ans = max(ans, leftup[i][j-K]+leftdown[i+K][j-K]+rightup[m-1][j]);
}
}
//上
for(int i=0;i<m-K;i++) {
for(int j=0;j<n-K;j++) {
ans = max(ans, leftup[i][n-1]+leftdown[i+K][j]+rightdown[i+K][j+K]);
}
}
//下
for(int i=K;i<m;i++) {
for(int j=0;j<n-K;j++) {
ans = max(ans, leftup[i-K][j]+rightup[i-K][j+K]+leftdown[i][n-1]);
}
}
System.out.println(ans);
}
}