题目：https://ac.nowcoder.com/acm/contest/888/A
题意：找全1矩阵的个数，并且这个全1矩阵不被其他全1矩阵包含
思路：这里引用付队说的话
-> {
这类问题，一般解决就是两个方向：
A：压缩一维，即枚举上下边界，然后复杂度O(N^3);
B：广告牌问题，即枚举下边界s，那么久可以看成s为底的一些高楼，再高楼上布置广告牌，复杂度O(N^2)。
}
这里光看复杂度我们就能看出肯定是B类问题，我们之前已经知道怎么求出每个矩阵了，但是我们怎么确定他是最大不可延伸的矩阵了呢，其实我们无非就是看当前矩阵是否还可以向上下左右延申，左右的话我们之前看过dp和栈的做法能找出L[i],R[i],我们本来就是从上往下来枚举的，上面延申已经不用考虑，我们预处理出来了，我们以当前层为底时怎么确定下面是否可以再延申呢。我们只要看下下面这行是否全部都是1即可，那么如何确定呢，前缀和判断是否等于区间长度，这样就可以了，如果等于说明可以再延申，如果不可以，矩形数+1
#include<bits/stdc++.h>
#define maxn 3005
#define mod 1000000007
using namespace std;
typedef int ll;
ll n,m;
char str[maxn][maxn];
ll dp[maxn][maxn];
int vis[maxn][maxn];
ll r[maxn],l[maxn],sum[maxn];
ll cnt;
ll q[maxn],head;
void get(int t){
head=;q[++head]=;
for(int i=;i<=m;i++){
while(head>&&dp[t][i]<=dp[t][q[head]]) head--;
l[i]=q[head]+;
q[++head]=i;
}
head=;q[++head]=m+;
for(int i=m;i>=;i--){
while(head>&&dp[t][i]<=dp[t][q[head]]) head--;
r[i]=q[head]-;
q[++head]=i;
}
for(int i=;i<=m;i++) sum[i]=sum[i-]+(str[t+][i]=='');
for(int i=;i<=m;i++){
if(dp[t][i]==) continue;
if(vis[l[i]][r[i]]==t) continue;
if(sum[r[i]]-sum[l[i]-]==r[i]-l[i]+) continue;
cnt++;
vis[l[i]][r[i]]=t;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%s",str[i]+);
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(str[i][j]==''){
dp[i][j]=dp[i-][j]+;
}
else dp[i][j]=;
}
}
for(int i=;i<=n;i++){
get(i);
}
printf("%d",cnt);
return ;
}