首页 > 其他 > 详细

[POJ1964]City Game (悬线法)

时间:2019-01-05 16:19:17      阅读:349      评论:0      收藏:0      [点我收藏+]

技术分享图片

题意

其实就是BZOJ3039 不过没权限号(粗鄙之语)

同时也是洛谷4147

就是求最大子矩阵然后*3

思路

悬线法

有个博客讲的不错https://blog.csdn.net/u012288458/article/details/48197727

GREED-VI大佬之前也讲过,友链一下https://www.cnblogs.com/GREED-VI/p/9887399.html (他说的其实是悬线法,扫描线和这个不一样的吧)

代码

水水水

#include<cstdio>
#include<iostream>
#include<cstring> 
#include<algorithm>
#define N 1005
using namespace std;
int n,m;
int ans;
int up[N][N],L[N][N],R[N][N];
pair<int,int> st[N];
bool v[N][N],f_fall;
void init()
{
    char ch;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        cin>>ch;
        v[i][j]=(ch==F?1:0);
        if(v[i][j]) f_fall=1;
    }
}
void solve()
{
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        if(!v[i][j])
            up[i][j]=0;
        else up[i][j]=up[i-1][j]+1;
    for (int i=1;i<=n;i++)
    {
        int top=0;
        st[++top]=make_pair(-1,0);
        for (int j=1;j<=m;j++)
        {
            while (up[i][j]<=st[top].first) top--;
            L[i][j]=j-st[top].second-1;
            st[++top]=make_pair(up[i][j],j);
        }
    }
    for (int i=1;i<=n;i++)
    {
        int top=0;
        st[++top]=make_pair(-1,m+1);
        for (int j=m;j>=1;j--)
        {
            while (up[i][j]<=st[top].first) top--;
            R[i][j]=st[top].second-j-1;
            st[++top]=make_pair(up[i][j],j);
        }
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    ans=max(ans,(L[i][j]+R[i][j]+1)*up[i][j]);
    ans*=3;
}
int main()
{
    //freopen("cpp.in","r",stdin);
    //freopen("cpp.out","w",stdout); 
    int Q;scanf("%d",&Q);
    while(Q--)
    {
        f_fall=0;
        init();
        if(f_fall==0) printf("0\n");
        else{
            solve();
            printf("%d\n",ans);
            ans=0;
            memset(v,0,sizeof(v));
            memset(up,0,sizeof(up));
            memset(L,0,sizeof(L));
            memset(R,0,sizeof(R));
            memset(st,0,sizeof(st));
        }
    }
    return 0;
} 

 

[POJ1964]City Game (悬线法)

原文:https://www.cnblogs.com/lincold/p/10224751.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!