郑州网站优化怎样做,登封seo推广,东坑镇仿做网站,品牌网络推广方案题目内容 原题链接 给定一个 n n n 行 m m m 列的矩阵#xff0c;问权值最大的子矩阵的权值是多少。
对于一个矩阵#xff0c;其权值定义为矩阵中的最小值 m i n v minv minv 乘上矩阵中所有元素的和。
数据范围 1 ≤ n , m ≤ 300 1\leq n,m \leq 300 1≤n,m≤300 1 ≤…题目内容 原题链接 给定一个 n n n 行 m m m 列的矩阵问权值最大的子矩阵的权值是多少。
对于一个矩阵其权值定义为矩阵中的最小值 m i n v minv minv 乘上矩阵中所有元素的和。
数据范围 1 ≤ n , m ≤ 300 1\leq n,m \leq 300 1≤n,m≤300 1 ≤ a i ≤ 300 1\leq a_i\leq 300 1≤ai≤300
题解
对于这类矩阵问题通常做法都是枚举矩阵的下边界和下边界这样就可以将矩阵看成一个一维数组问题。
考虑对于一个一维数组找到其中一个子数组连续子序列满足子数组的最小值乘上子数组的元素和最大。
那么问题就非常显然了考虑数组中每个元素作为子数组的最小值考虑这个子数组的左右端点就是考虑其左边和右边第一个小于其的元素即可。这个就是单调栈的经典应用单调栈在这里是 O ( m ) O(m) O(m) 的。
时间复杂度 O ( n 2 m ) O(n^2m) O(n2m)
代码
#include bits/stdc.h
using namespace std;const int N 310;
int a[N][N];
// 列前缀和
int col[N][N];
int stk[N];
// up ~ down 这个上下界内每个列左边第一个小于该列最小值的列
int L[N], R;
// up ~ down 这个上下界内每个列的元素之和 的前缀和
int pre[N];
// up ~ down 这个上下界内每个列的最小值
int cmin[N];// up ~ down 内一个列的元素和
int up, down;
int v(int idx) {return col[down][idx] - col[up - 1][idx];
}int main()
{int n, m;cin n m;for (int i 1; i n; i)for (int j 1; j m; j) {cin a[i][j];// 每一行的前缀和col[i][j] col[i - 1][j] a[i][j];}long long ans 0;// 枚举子矩阵的上下边界for (up 1; up n; up) {for (int j 1; j m; j) cmin[j] a[up][j];for (down up; down n; down) {// 每一列的最小值for (int j 1; j m; j) cmin[j] min(cmin[j], a[down][j]);int top 0;for (int j 1; j m; j) {while (top 0 cmin[stk[top]] cmin[j]) top - 1;if (top 0) L[j] 1;else L[j] stk[top] 1;stk[top] j;// 每一行的前缀和pre[j] pre[j - 1] v(j);}top 0;for (int j m; j 1; --j) {while (top 0 cmin[stk[top]] cmin[j]) top - 1;if (top 0) R m;else R stk[top] - 1;stk[top] j;ans max(ans, 1ll * (pre[R] - pre[L[j] - 1]) * cmin[j]);}}}cout ans \n;return 0;
}
