题目链接 2017 Beijing Problem H
题意 给定一个$n * m$的矩阵，现在可以把矩阵中的任意一个数换成$p$，求替换之后最大子矩阵的最小值。
首先想一想暴力的方法，枚举矩阵中的数，然后$O(n^{3})$求最大子矩阵更新答案，这样复杂度是$O(n^{5})$的。
思考得再仔细一些，就是包含这个数的最大子矩阵和，以及不包含这个数的最大子矩阵的和的较大值。
设原矩阵中最大子矩阵和为$mx$。
设$u_{i}$为只考虑矩阵前$i$行的最大子矩阵和，$d_{i}$为考虑矩阵第$i$行到第$n$行的最大子矩阵和，
$l_{i}$为只考虑矩阵前$i$列的最大子矩阵和，$r_{i}$为考虑矩阵第$i$列到第$m$列的最大子矩阵和。
那么枚举某个格子的时候不经过这个格子的最大子矩阵和为$max(u_{i-1}, d_{i+1}, l_{j-1}, r_{j+1})$
枚举的时候，当$a_{i,j} <= p$时，显然不起作用，跳过。
当$a_{i,j} > p$时，分类讨论：
（1）当$a_{i,j}$被原矩阵的最大子矩阵包含的时候，此时最大子矩阵和被更新为$mx - a_{i,j} + p$
（2）当$a_{i,j}$不被原矩阵的最大子矩阵包含的时候，
此时$mx - a_{i,j} + p < mx = max(u_{i-1}, d_{i+1}, l_{j-1}, r_{j+1})$，对答案不产生影响，
所以直接枚举$a_{i,j}$，更新答案即可。
时间复杂度$O(n^{3})$
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; const int N = 153; int n, m, p; int a[N][N], s[N][N], t[N][N]; int l[N], r[N], u[N], d[N], c[N]; int ans, now; int main(){ while (~scanf("%d%d%d", &n, &m, &p)){ rep(i, 1, n){ rep(j, 1, m) scanf("%d", a[i] + j); } memset(s, 0, sizeof s); rep(i, 1, n){ s[i][0] = 0; rep(j, 1, m) s[i][j] = s[i][j - 1] + a[i][j]; } memset(t, 0, sizeof t); rep(j, 1, m){ t[j][0] = 0; rep(i, 1, n) t[j][i] = t[j][i - 1] + a[i][j]; } rep(i, 0, max(n, m) + 3){ u[i] = -2e9; d[i] = -2e9; l[i] = -2e9; r[i] = -2e9; } rep(i, 1, m){ rep(j, i, m){ memset(c, 0, sizeof c); rep(k, 1, n){ c[k] = max(c[k - 1] + s[k][j] - s[k][i - 1], s[k][j] - s[k][i - 1]); } rep(k, 1, n) u[k] = max(u[k], c[k]); } } rep(i, 1, m){ rep(j, i, m){ memset(c, 0, sizeof c); dec(k, n, 1){ c[k] = max(c[k + 1] + s[k][j] - s[k][i - 1], s[k][j] - s[k][i - 1]); } rep(k, 1, n) d[k] = max(d[k], c[k]); } } rep(i, 1, n){ rep(j, i, n){ memset(c, 0, sizeof c); rep(k, 1, m){ c[k] = max(c[k - 1] + t[k][j] - t[k][i - 1], t[k][j] - t[k][i - 1]); } rep(k, 1, m) l[k] = max(l[k], c[k]); } } rep(i, 1, n){ rep(j, i, n){ memset(c, 0, sizeof c); dec(k, m, 1){ c[k] = max(c[k + 1] + t[k][j] - t[k][i - 1], t[k][j] - t[k][i - 1]); } rep(k, 1, m) r[k] = max(r[k], c[k]); } } rep(i, 1, n){ u[i] = max(u[i], u[i - 1]); } dec(i, n, 1){ d[i] = max(d[i], d[i + 1]); } rep(i, 1, m){ l[i] = max(l[i], l[i - 1]); } dec(i, m, 1){ r[i] = max(r[i], r[i + 1]); } ans = 2e9; rep(i, 1, n){ rep(j, 1, m){ now = -2e9; now = max(now, l[j - 1]); now = max(now, r[j + 1]); now = max(now, u[i - 1]); now = max(now, d[i + 1]); now = max(now, u[n] - a[i][j] + p); ans = min(ans, now); } } ans = min(ans, u[n]); printf("%d\n", ans); } return 0; }
转载于:https://www.cnblogs.com/cxhscst2/p/9102699.html
