http://hihocoder.com/contest/icpcbeijing2017/problem/8

预处理暴力枚举修改的点

#include 
     
      using namespace std;const int maxn = 159;const int inf = 0x3f3f3f3f;int a[maxn][maxn];int colsum[maxn][maxn];int rowsum[maxn][maxn];int dp[maxn];int up[maxn],down[maxn],rig[maxn],lef[maxn];int main(){    int n,m,p;    while(~scanf("%d%d%d",&n,&m,&p)){        memset(up,-inf,sizeof(up));        memset(down,-inf,sizeof(down));        memset(rig,-inf,sizeof(rig));        memset(lef,-inf,sizeof(lef));        for(int i=1;i<=n;i++){            for(int j=1;j<=m;j++){                scanf("%d",&a[i][j]);                colsum[i][j] = colsum[i-1][j]+a[i][j];                rowsum[i][j] = rowsum[i][j-1]+a[i][j];            }        }        int ans = -inf;        for(int i=1;i<=n;i++){            for(int j=i;j<=n;j++){                dp[0] = -inf;                for(int k=1;k<=m;k++){                    int tmp  =colsum[j][k]-colsum[i-1][k];                    dp[k] = max(dp[k-1]+tmp,tmp);                    ans = max(ans,dp[k]);                    lef[k] = max(lef[k],dp[k-1]);                }            }        }        for(int i=1;i<=n;i++){            for(int j=i;j<=n;j++){                dp[m+1] = -inf;                for(int k=m;k>=1;k--){                    int tmp  =colsum[j][k]-colsum[i-1][k];                    dp[k] = max(dp[k+1]+tmp,tmp);                    rig[k] = max(rig[k],dp[k+1]);                }            }        }        for(int i=1;i<=m;i++){            for(int j=i;j<=m;j++){                dp[0] = -inf;                for(int k=1;k<=n;k++){                    int tmp  =rowsum[k][j]-rowsum[k][i-1];                    dp[k] = max(dp[k-1]+tmp,tmp);                    up[k] = max(up[k],dp[k-1]);                }            }        }        for(int i=1;i<=m;i++){            for(int j=i;j<=m;j++){                dp[n+1] = -inf;                for(int k=n;k>=1;k--){                    int tmp  =rowsum[k][j]-rowsum[k][i-1];                    dp[k] = max(dp[k+1]+tmp,tmp);                    down[k] = max(down[k],dp[k+1]);                }            }        }        for(int i=1;i<=m;i++){            lef[i] = max(lef[i],lef[i-1]);        }        for(int i=m;i>=1;i--){            rig[i] = max(rig[i],rig[i+1]);        }        for(int i=1;i<=n;i++){            up[i] = max(up[i],up[i-1]);        }        for(int i=n;i>=1;i--){            down[i] = max(down[i],down[i+1]);        }        int ret = ans;        for(int i=1;i<=n;i++){            for(int j=1;j<=m;j++){                int tmp = max(up[i],down[i]);                tmp  = max(tmp,lef[j]);                tmp = max(tmp,rig[j]);                tmp = max(tmp,ans-a[i][j]+p);                ret = min(ret,tmp);            }        }        printf("%d\n",ret);    }    return 0;}/*1 4 -13 -2 5 9*/