51 nod 1158 全是1的最大子矩阵

可以把问题转化成poj2559的这种问题,然后按照每行去计算。
推荐一篇blog
链接说明

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long ll;
typedef double dl;

const int N = 1e5+7;
const int M = 1e9+7;
const int INF = 0x7fffffff;

int n,m;
int h[N];
int a[N];
stack<int> st;
void solve()
{
    scanf("%d%d",&n,&m);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int x;
            scanf("%d",&x);
            if(x==1) h[j]=h[j]+1;
            else h[j]=0;
            a[j]=h[j];
        }
        a[m+1]=-1;
        for(int j=1;j<=m+1;j++)
        {

            if(st.empty()||a[j]>=a[st.top()])
            {
                st.push(j);
            }
            else 
            {
                int top;
                while(!st.empty()&&a[j]<a[st.top()])
                {
                    top=st.top();
                    ans=max(ans,((j-top)*a[top]));    
                    st.pop();
                }
                st.push(top);
                a[top]=a[j];
            }
        }
    } 
    printf("%d\n",ans);


}

int main()
{
    solve();
}
全部评论

相关推荐

07-02 18:09
门头沟学院 Java
苍穹外卖和谷粒商城这俩是不是烂大街了,还能做吗?
想去重庆的鸽子在吐槽:你不如把这俩做完自己搞明白再优化点再来问 何必贩卖焦虑
点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务