【算法分析】
这个要想想。。。
首先我们注意到，必然有一条竖线或者横线把3个矩形分成一边一个，一边两个的情况，于是预处理，然后再分类讨论即可。。。
【CODE】
#include
int m,n,k;
int w[N][N],sum[N][N],lu1[N][N],rd1[N][N];
int ru1[N][N],ld1[N][N],lu2m[N],lu2n[N],rd21[N],rd22[N];
inline int max(int x,int y){
if (x>y) return x;
return y;
}
void input(){
scanf("%d%d%d",&m,&n,&k);
int i,j;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++) scanf("%d",&w[i][j]);
memset(rd21,200,sizeof(rd21));
memset(lu2m,200,sizeof(lu2m));
memset(rd22,200,sizeof(rd22));
memset(lu2n,200,sizeof(lu2n));
memset(lu1,200,sizeof(lu1));
memset(rd1,200,sizeof(rd1));
memset(ld1,200,sizeof(ld1));
memset(ru1,200,sizeof(ru1));
}
void change(){
int i,j;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+w[i][j];
m=m-k+1; n=n-k+1;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
w[i][j]=sum[i+k-1][j+k-1]-sum[i-1][j+k-1]-sum[i+k-1][j-1]+sum[i-1][j-1];
}
void init(){
int i,j;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++){
lu1[i][j]=max(lu1[i-1][j],lu1[i][j-1]);
lu1[i][j]=max(lu1[i][j],w[i][j]);
}
for (i=m;i>=1;i–)
for (j=n;j>=1;j–){
rd1[i][j]=max(rd1[i+1][j],rd1[i][j+1]);
rd1[i][j]=max(rd1[i][j],w[i][j]);
}
for (i=1;i<=m;i++)
for (j=n;j>=1;j–){
ru1[i][j]=max(ru1[i-1][j],ru1[i][j+1]);
ru1[i][j]=max(ru1[i][j],w[i][j]);
}
for (i=m;i>=1;i–)
for (j=1;j<=n;j++){
ld1[i][j]=max(ld1[i+1][j],ld1[i][j-1]);
ld1[i][j]=max(ld1[i][j],w[i][j]);
}
//处理lu
for (j=1;j<=n;j++){
int &t=lu2m[j];
t=lu2m[j-1];
for (i=1;i<=m;i++){
if (i>k) t=max(t,lu1[i-k][j]+w[i][j]);
if (j>k) t=max(t,lu1[m][j-k]+w[i][j]);
if (i+k<=m) t=max(t,ld1[i+k][j]+w[i][j]);
}
}
for (i=1;i<=m;i++){
int &t=lu2n[i];
t=lu2n[i-1];
for (j=1;j<=n;j++){
if (j>k) t=max(t,lu1[i][j-k]+w[i][j]);
if (i>k) t=max(t,lu1[i-k][n]+w[i][j]);
if (j+k<=n) t=max(t,ru1[i][j+k]+w[i][j]);
}
}
//处理rd
for (j=n;j>=1;j–){
int &t=rd21[j];
t=rd21[j+1];
for (i=1;i<=m;i++){
if (i>k) t=max(t,ru1[i-k][j]+w[i][j]);
if (j+k<=n) t=max(t,rd1[1][j+k]+w[i][j]);
if (i+k<=m) t=max(t,rd1[i+k][j]+w[i][j]);
}
}
for (i=m;i>=1;i–){
int &t=rd22[i];
t=rd22[i+1];
for (j=1;j<=n;j++){
if (j+k<=n) t=max(t,rd1[i][j+k]+w[i][j]);
if (i+k<=m) t=max(t,rd1[i+k][1]+w[i][j]);
if (j>k) t=max(t,ld1[i][j-k]+w[i][j]);
}
}
}
void work(){
int ans=0,i,j;
for (i=1;i+k<=m;i++){
ans=max(ans,lu1[i][n]+rd22[i+k]);
ans=max(ans,lu2n[i]+rd1[i+k][1]);
}
for (j=1;j+k<=n;j++){
ans=max(ans,lu1[m][j]+rd21[j+k]);
ans=max(ans,lu2m[j]+rd1[1][j+k]);
}
printf("%dn",ans);
}
int main(){
freopen("oil.in","r",stdin);
freopen("oil.out","w",stdout);
input();
change();
init();
work();
}