题意：给一个n*m的矩阵，你只能选择一个格子把这个格子的数换成p（也可以一个都不换），问最大子矩阵和最小可能是多少？
思路：
思路就是上面这个思路，这里简单讲一下怎么n^3求最大子矩阵和：枚举两行（或者两列），然后把每一列之和看做一个数字，这样二维就变成了一维，我们可以直接求最大子串和的方法。初始一个ret为0，然后从左往右加，如果ret<0，那么把ret初始化0，负数作为初始值肯定比重新开始小，然后找出ret的最大值就是最大子矩阵和。
代码：
#include<cstdio>
#include<cstring>
typedef long long ll;
using namespace std;
const int maxn = + ;
const int MOD = 1e9 + ;
const int INF = 0x3f3f3f3f;
int num[maxn][maxn], sum[maxn][maxn];
int up[maxn], down[maxn], left[maxn], right[maxn];
int n, m, p, xx1, yy1, xx2, yy2;
int min(int x, int y){
return x < y? x : y;
}
int max(int x, int y){
return x > y? x : y;
}
int mat(int x1, int y1, int x2, int y2){
return sum[x2][y2] - sum[x1 - ][y2] - sum[x2][y1 - ] + sum[x1 - ][y1 - ];
}
int main(){
while(~scanf("%d%d%d", &n, &m, &p)){
memset(sum, , sizeof(sum));
for(int i = ; i <= n; i++){
for(int j = ; j <= m; j++){
scanf("%d", &num[i][j]);
sum[i][j] = num[i][j] + sum[i - ][j] + sum[i][j - ] - sum[i - ][j - ];
}
} //上下左右四个矩阵预处理
memset(up, -INF ,sizeof(up));
for(int i = ; i <= n; i++){
int tmp = -INF;
for(int j = ; j <= i; j++){
int ret = ;
for(int k = ; k <= m; k++){
ret += mat(j, k, i, k);
tmp = max(tmp, ret);
if(ret < ) ret = ;
}
}
up[i] = max(up[i - ], tmp);
}
memset(down, -INF, sizeof(down));
for(int i = n; i >= ; i--){
int tmp = -INF;
for(int j = i; j <= n; j++){
int ret = ;
for(int k = ; k <= m; k++){
ret += mat(i, k, j, k);
tmp = max(tmp, ret);
if(ret < ) ret = ;
}
}
down[i] = max(down[i + ], tmp);
}
memset(left, -INF, sizeof(left));
for(int i = ; i <= m; i++){
int tmp = -INF;
for(int j = ; j <= i; j++){
int ret = ;
for(int k = ; k <= n; k++){
ret += mat(k, j, k, i);
tmp = max(ret, tmp);
if(ret < ) ret = ;
}
}
left[i] = max(left[i - ], tmp);
}
memset(right, -INF, sizeof(right));
for(int i = m; i >= ; i--){
int tmp = -INF;
for(int j = i; j <= m; j++){
int ret = ;
for(int k = ; k <= n; k++){
ret += mat(k, i, k, j);
tmp = max(ret, tmp);
if(ret < ) ret = ;
}
}
right[i] = max(right[i + ], tmp);
} int Max = -INF;
for(int i = ; i <= n; i++){
for(int j = ; j <= i; j++){
int ret = , start = ;;
for(int k = ; k <= m; k++){
ret += mat(j, k, i, k);
if(ret > Max){
Max = ret;
xx1 = j, yy1 = start, xx2 = i, yy2 = k;
}
if(ret < ) ret = , start = k + ;
}
}
}
int ans = Max;
for(int i = xx1; i <= xx2; i++){
for(int j = yy1; j <= yy2; j++){
if(p > num[i][j]) continue;
ans = min(ans , max(Max - num[i][j] + p, max(up[i - ], max(down[i + ], max(left[j - ], right[j + ])))));
}
}
printf("%d\n", ans);
}
return ;
}