[HOJ] 233 - Oil [ZJ] a026: APIO2009 1.采油区域

#include<stdio.h>
#include<algorithm>
using namespace std;
int s[1505][1505],add[1505][1505]={0},dp[5][1505][1505]={0},L[1505]={0},R[1505]={0};
int main(){
    int n,m,t,i,j,k,ans=0,x=0;
    scanf("%d%d%d",&n,&m,&t);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            scanf("%d",&s[i][j]);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            add[i][j]=add[i-1][j]+add[i][j-1]-add[i-1][j-1]+s[i][j];
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        if(i>=t && j>=t){
            dp[1][i][j]=max(dp[1][i-1][j],dp[1][i][j-1]);
            dp[1][i][j]=max(dp[1][i][j],add[i][j]-add[i-t][j]-add[i][j-t]+add[i-t][j-t]);
        }
    for(i=1;i<=n;i++)
        for(j=m;j>=1;j--)
        if(i>=t && j<=m-t+1){
            dp[2][i][j]=max(dp[2][i-1][j],dp[2][i][j+1]);
            dp[2][i][j]=max(dp[2][i][j],add[i][j+t-1]-add[i-t][j+t-1]-add[i][j-1]+add[i-t][j-1]);
        }
    for(i=n;i>=1;i--)
        for(j=1;j<=m;j++)
        if(i<=n-t+1 && j>=t){
            dp[3][i][j]=max(dp[3][i+1][j],dp[3][i][j-1]);
            dp[3][i][j]=max(dp[3][i][j],add[i+t-1][j]-add[i+t-1][j-t]-add[i-1][j]+add[i-1][j-t]);
        }
    for(i=n;i>=1;i--)
        for(j=m;j>=1;j--)
        if(i<=n-t+1 && j<=m-t+1){
            dp[4][i][j]=max(dp[4][i+1][j],dp[4][i][j+1]);
            dp[4][i][j]=max(dp[4][i][j],add[i+t-1][j+t-1]-add[i+t-1][j-1]-add[i-1][j+t-1]+add[i-1][j-1]);
        }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++){
            k=ans;
            ans=max(ans,dp[1][i][j]+dp[2][i][j+1]+dp[3][i+1][m]);
            ans=max(ans,dp[2][i][j+1]+dp[4][i+1][j+1]+dp[1][n][j]);
            ans=max(ans,dp[3][i+1][j]+dp[4][i+1][j+1]+dp[1][i][m]);
            ans=max(ans,dp[1][i][j]+dp[3][i+1][j]+dp[2][n][j+1]);
        }
    for(j=t;j<=m;j++){
        for(i=t;i<=n;i++){
            L[j]=max(L[j],add[i][j]-add[i-t][j]-add[i][j-t]+add[i-t][j-t]);
            R[i]=max(R[i],add[i][j]-add[i-t][j]-add[i][j-t]+add[i-t][j-t]);
        }
    }
    for(i=1;i<=m;i++){
        x=0;
        for(j=i+t;j<m;j++){
            x=max(x,L[j]);
            ans=max(ans,dp[1][n][i]+x+dp[2][n][j+1]);
        }
    }
    for(i=1;i<=n;i++){
        x=0;
        for(j=i+t;j<n;j++){
            x=max(x,R[j]);
            ans=max(ans,dp[1][i][m]+x+dp[3][j+1][m]);
        }
    }
    printf("%d\n",ans);
}