http://hihocoder.com/contest/icpcbeijing2017/problem/8
預處理暴力枚舉修改的點
#include <bits/stdc++.h>
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 -1
3 -2 5 9
*/
