网站从建设到运营管理的理解,网站版式分类,发布网站域名设置,购物网站后台订单处理流程H - Maximal submatrix HDU - 6957
题意#xff1a;
给定一个n行m列的矩阵#xff0c;求每列上面积不减的最大子矩阵
对于每个测试用例#xff0c;打印一个表示最大子矩阵的整数
题解#xff1a;
要求求一个最大面积的满足每列非递减的矩阵#xff0c;这怎么想#…H - Maximal submatrix HDU - 6957
题意
给定一个n行m列的矩阵求每列上面积不减的最大子矩阵
对于每个测试用例打印一个表示最大子矩阵的整数
题解
要求求一个最大面积的满足每列非递减的矩阵这怎么想 我们可以转化成01矩阵每一个位置1表示该位置比上面一位大然后求最大的01矩阵就可以了单调栈做法时注意0的话可以作为矩阵的开始详细看看代码
代码
单调栈做法
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;
//Fe~Jozky
const ll INF0x3f3f3f3f;
inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
int n,m;
const int maxn2e39;
int a[maxn][maxn];
int h[maxn][maxn];
int w[maxn][maxn];
int st[maxn],top;
int ans0;
void precal(){memset(w,0,sizeof(w));for(int i1;in;i){for(int j1;jm;j){if(h[i][j]0)w[i][j]1;else w[i][j]w[i-1][j]1;}w[i][m1]-1; }
}
void cal(){for(int i1;in;i){top0;for(int j1;jm1;j){if(top0||w[i][j]w[i][st[top]]){st[top]j;}else {int id;while(top!0w[i][j]w[i][st[top]]){idst[top];top--;ansmax(ans,(j-id)*w[i][id]);}st[top]id;w[i][id]w[i][j];}}}
}
void solve(){nread();mread();for(int i1;in;i){for(int j1;jm;j){a[i][j]read();}}for(int i1;in;i){for(int j1;jm;j){if(a[i][j]a[i-1][j])h[i][j]1;else h[i][j]0;}}precal();cal(); coutansendl;
}
int main()
{#ifdef ONLINE_JUDGE#elsefreopen(1.in,r,stdin);#endifint t;tread();while(t--){ans0;solve();}fclose(stdin);return 0;
}纵向的悬线法
#include iostream
#include cstring
#define FAST ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define endl \n
#define debug(x) cout #x (x) endl
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)(b)?(a):(b))
#define min(a,b) ((a)(b)?(a):(b))
#define rep(i,a,n) for(int ia;in;i)
#define per(i,n,a) for(int in;ia;--i)using namespace std;const int maxn 2e35;int n, m;
short a[maxn][maxn];
bool b[maxn][maxn];
short up[maxn][maxn], down[maxn][maxn], len[maxn][maxn];void tran() {mem(b, 0);rep(i, 1, n) {rep(j, 1, m) {if (i 1) continue;else if (a[i][j] a[i-1][j]) b[i][j] 1;}}
}void init() {rep(i, 1, n) {rep(j, 1, m) {up[i][j] i;down[i][j] i;len[i][j] 1;}}
}int main()
{FAST;int t; cin t;while (t--) {cin n m;rep(i, 1, n) {rep(j, 1, m) {cin a[i][j];}}tran();init();rep(j, 1, m) {rep(i, 2, n) {if (b[i][j]) up[i][j] up[i-1][j];}per(i, n-1, 1) {if (b[i1][j]) down[i][j] down[i1][j];}}int ans m;rep(j, 1, m) {rep(i, 1, n) {if (b[i][j-1]) {len[i][j] len[i][j-1] 1;up[i][j] max(up[i][j], up[i][j-1]);down[i][j] min(down[i][j], down[i][j-1]);}int llen down[i][j] - up[i][j] 1;ans max(ans, llen * len[i][j]);}}cout ans endl;}return 0;
}
另一种悬线法
写法就是对于每一行的最大范围就是两侧0之间我们设高度一开始为0是因为每一个矩阵第一行是可以有0的但是之后不可以所以我们最后得到的高度还要算上第一行。相当于我们刨去第一行考虑01矩阵最后再算上第一行 比如01矩阵
01011
01110
11111我们先不考虑第一行然后考虑后两行的左右宽度和高左2右为4高为2那么答案就是(4-21)*(21)
#includeiostream
#includecstdio
#includecstring
#includecmath
using namespace std;
typedef long long ll;
const int maxn2e310;
int t,n,m;
int l[maxn][maxn];
int le[maxn][maxn];
int r[maxn][maxn];
int h[maxn][maxn];
int main()
{cint;while(t--){cinnm;memset(le,0,sizeof(le));for(int i1;in;i){for(int j1;jm;j){le[0][j]0;scanf(%d,l[i][j]);if(i!1)if(l[i][j]l[i-1][j]){le[i][j]1;}//else le[i][j]1;}}memset(l,0,sizeof(l));memset(h,0,sizeof(h));memset(r,0,sizeof(r));int ansm;int L1e9,R0;for(int i1;in;i){for(int j1;jm;j){if(le[i][j]1){Lmin (L,j);}else L1e9;l[i][j]L;//如果当前点为0左端点取正无穷 }for(int jm;j1;j--){if(le[i][j]1){Rmax(R,j);}else R0;r[i][j]R;//如果当前端点为0右端点取无穷小 }for(int j1;jm;j){if(le[i-1][j]1){h[i][j]h[i-1][j]1;l[i][j]max(l[i-1][j],l[i][j]);r[i][j]min(r[i-1][j],r[i][j]);}else h[i][j]1;if(le[i][j]1){ansmax(ans,(r[i][j]-l[i][j]1)*(h[i][j]1));}}} coutansendl;}return 0;
}
