题目描述
萌萌哒的Created equal是一只小仓鼠，小仓鼠自然有仓鼠窝啦。
仓鼠窝是一个由n*m个格子组成的行数为n、列数为m的矩阵。小仓鼠现在想要知道，这个矩阵中有多少个子矩阵！（实际上就是有多少个子长方形嘛。）比如说有一个2*3的矩阵，那么1*1的子矩阵有6个，1*2的子矩阵有4个，1*3的子矩阵有2个，2*1的子矩阵有3个，2*2的子矩阵有2个，2*3的子矩阵有1个，所以子矩阵共有6+4+2+3+2+1=18个。
可是仓鼠窝中有的格子被破坏了。现在小仓鼠想要知道，有多少个内部不含被破坏的格子的子矩阵！
输入输出格式
输入格式：
第一行两个正整数n和m，分别表示仓鼠窝的行数n、列数m。
接下来n行，每行m个数，每个数代表对应的格子，非0即1。若为0，表示这个格子被破坏；反之代表这个格子是完好无损的。
输出格式：
仅一个正整数，表示未被破坏的子矩阵的个数。
分析
代码
注意要开long long和常数优化。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> pa; const int maxn=3000+5; inline void read(int &x){ x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} } int n,m,top; ll cnt,ans; int A[maxn][maxn],pre[maxn][maxn],H[maxn]; pa sta[maxn]; int main(){ read(n);read(m); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) read(A[i][j]); for(int i=1;i<=n;++i){ cnt=0;top=0; pa tmp; for(int j=1;j<=m;++j){ if(!A[i][j]){H[j]=0; cnt=0;top=0;continue;} tmp.fi=++H[j]; tmp.se=1; while(top&&sta[top].fi>=tmp.fi){ tmp.se=tmp.se+sta[top].se; cnt-=1ll*sta[top].fi*sta[top].se; top--; } sta[++top]=tmp; cnt+=1ll*tmp.fi*tmp.se; ans+=cnt; } } printf("%lld ",ans); return 0; }