I. Sequence 题解(思维+矩阵内全0正方形的数量)

题目链接

题目思路

看起来很难，其实转换问题就是个矩阵内全0正方形的数量

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=5e3+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n,m;
int a[maxn][maxn];
int h[maxn][maxn];
int l[maxn];
int dp[maxn];
signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        a[u][v]=1;
    }
    for(int j=1;j<=n;j++){
        for(int i=1;i<=n;i++){
            if(a[i][j]){
                h[i][j]=0;
            }else{
                h[i][j]=h[i-1][j]+1;
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        stack<int> sta;
        for(int j=1;j<=n;j++){
            while(!sta.empty()&&h[i][sta.top()]>=h[i][j]){
                sta.pop();
            }
            l[j]=sta.empty()?0:sta.top();
            sta.push(j);
            dp[j]=(j-l[j])*h[i][j]+dp[l[j]];
            ans=ans+dp[j];
        }
    }
    printf("%lld
",ans);
    return 0;
}