首页 > 代码库 > 洛谷U4859matrix[单调栈]
洛谷U4859matrix[单调栈]
题目描述
给一个元素均为正整数的矩阵，上升矩阵的定义为矩阵中每行、每列都是严格递增的。
求给定矩阵中上升子矩阵的数量。
输入输出格式
输入格式：
第一行两个正整数n、m，表示矩阵的行数、列数。
接下来n行，每行m个正整数表示矩阵中的元素。
输出格式：
一个数表示数量。
输入输出样例
输入样例#1：
4 41 2 3 42 3 4 53 4 5 64 5 6 7
输出样例#1：
100
出题人的题解是O(n3)
感觉可以用单调栈做O(n2)，果真可以
和仓鼠那道比较像
只是需要维护两个tot，一个是只考虑上下单增，另一个tot2同时考虑左右单增，合并时只能用tot2
如果tot>tot2还要给这个节点再加一个
//// main.cpp// luoguU4859//// Created by Candy on 10/10/16.// Copyright © 2016 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;typedef long long ll;const int N=355;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x;}int n,m,a[N][N];// 0<a[i][j]struct data{ int l,h;}st[N];int top=0,tot[N],tot2[N];ll ans=0;int main(int argc, const char * argv[]) { n=read();m=read(); memset(a,-1,sizeof(a)); for(int i=1;i<=n;i++){ top=0; ll cnt=0; for(int j=1;j<=m;j++){ a[i][j]=read(); if(a[i][j]<=a[i-1][j]) tot[j]=tot2[j]=0; tot[j]++;tot2[j]++; if(a[i][j]<=a[i][j-1]){top=0;cnt=0;tot2[j]=0;} data tmp; tmp.h=tot2[j]; if(tot[j]==tot2[j]) tmp.l=1; else tmp.l=0; while(top&&st[top].h>=tmp.h){ tmp.l+=st[top].l; cnt-=st[top].l*st[top].h; top--; } st[++top]=tmp; cnt+=tmp.l*tmp.h; if(tot[j]>tot2[j]){ cnt+=1*tot[j]; st[++top].h=tot[j]; st[top].l=1; } ans+=cnt; //printf("h %d %d %d %d\n",i,j,tot[j],tot2[j]); //printf("i %d %d %d %d\ncnt %d\n",i,j,tmp.l,tmp.h,cnt); } //printf("ans %d\n",ans); } printf("%lld",ans); return 0;}
洛谷U4859matrix[单调栈]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。