前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >POJ 1964&HDU 1505&HOJ 1644 City Game(最大0,1子矩阵和总结)

POJ 1964&HDU 1505&HOJ 1644 City Game(最大0,1子矩阵和总结)

作者头像
ShenduCC
发布2018-04-26 11:21:58
8230
发布2018-04-26 11:21:58
举报
文章被收录于专栏:算法修养

最大01子矩阵和,就是一个矩阵的元素不是0就是1,然后求最大的子矩阵,子矩阵里的元素都是相同的。 这个题目,三个oj有不同的要求,hoj的要求是5s,poj是3秒,hdu是1秒。不同的要求就对应不同的难度,不同的逼格。 先看最low的, HOJ 1664 5秒钟的时间,够长了。我很容易想到可以最大子矩阵和来求解,二者本来就很像,关于最大子矩阵和这个博客里有介绍 最大子矩阵和 这里我们可以把F变成1,把R变成负无穷大,这样求解最大子矩阵和就可以得到答案

代码语言:javascript
复制
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>

using namespace std;
#define MAX -1005
int a[1005][1005];
int dp[1005];
int c[1005];
char b[105];
int n,m;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
       // getchar();
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%s",b);
                if(b[0]=='R')
                    a[i][j]=MAX;
                else if(b[0]=='F')
                    a[i][j]=1;
            }
            //getchar();
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            memset(c,0,sizeof(c));
            memset(dp,0,sizeof(dp));
            for(int k=i;k<=n;k++)
            {
                for(int j=1;j<=m;j++)
                {
                    c[j]+=a[k][j];
                    if(dp[j-1]>=0)
                        dp[j]=dp[j-1]+c[j];
                    else
                        dp[j]=c[j];
                    ans=max(ans,dp[j]);
                }
            }
        }
        printf("%d\n",ans*3);
    }
    return 0;
}

这个代码在poj上也可以过大概是2秒多,差一点就超时。效率是O(n^3).

这里写图片描述
这里写图片描述

但是我们怎么能止步于此呢! 接下来这道题目可以用O(n^2)效率解决。首先F是1,R是0。其思想是把1看成一个方块,0自然就没有方块,整个矩阵从第一维开始,然后逐维的加上,就是一排高度不一的矩形。从这一排矩形找到可以形成的最大矩形,就是转换为poj2082 可以看这篇博客 POJ 2082

代码语言:javascript
复制
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>

using namespace std;
#define MAX 1000
int a[MAX+5][MAX+5];
int c[MAX+5];
int n,m;
char b[25];
int ans;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        //getchar();
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%s",b);
                if(b[0]=='F')
                    a[i][j]=1;
                else
                    a[i][j]=0;
            }
            //getchar();
        }
        memset(c,0,sizeof(c));
        ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
               if(a[i][j]==1)
                   c[j]++;
                else
                   c[j]=0;
            }
            int sum=0;
            for(int k=1;k<=m;k++)
            {
                int num=0;
                for(int p=k-1;p>=1;p--)
                {
                    if(c[p]>=c[k])
                        num++;
                    else
                        break;
                }

                for(int q=k+1;q<=m;q++)
                {
                    if(c[q]>=c[k])
                        num++;
                    else
                        break;
                }
                num++;
                num*=c[k];
                //cout<<num<<endl;
                sum=max(sum,num);
            }
            ans=max(ans,sum);
            //printf("%d\n",ans);
        }
        printf("%d\n",ans*3);
    }
    return 0;
}
这里写图片描述
这里写图片描述

果然快了1秒多,但是HDU里要求是1秒,但是hdu的数据没有那么大,这个代码交到hdu是可以过的,但是我们怎么可以止步于此,于是我们探究O(n)效率的算法。 其实把这道题目和poj 2082联系在一起就知道O(n)效率怎么写的了,利用单调栈,在求一排高度不等的矩形求形成最大矩形的效率是O(n).

这里写图片描述
这里写图片描述

根据递增的单调栈,如果当前栈顶的矩形高度高直接入栈

这里写图片描述
这里写图片描述

如果低于栈顶的矩形,那就出栈直到栈顶矩形高度低于当前矩形

代码语言:javascript
复制
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>

using namespace std;
#define MAX 1000
int a[MAX+5][MAX+5];
int c[MAX+5];
int n,m;
char b[25];
int ans;
int s[MAX+5];
int l[MAX+5];
int rear;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        //getchar();
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%s",b);
                if(b[0]=='F')
                    a[i][j]=1;
                else
                    a[i][j]=0;
            }
            //getchar();
        }
        memset(c,0,sizeof(c));
        ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
               if(a[i][j]==1)
                   c[j]++;
                else
                   c[j]=0;
            }
            rear=0;
            s[rear]=c[1];
            l[rear++]=1;
            for(int k=2;k<=m;k++)
            {
                if(c[k]>s[rear-1])
                {s[rear]=c[k];l[rear++]=1;}
                else
                {
                    int num=0;
                    while(c[k]<=s[rear-1])
                    {
                        num+=l[rear-1];
                        ans=max(ans,num*s[rear-1]);
                        rear--;
                        if(rear==0)
                            break;
                    }
                    s[rear]=c[k];
                    l[rear++]=num+1;
                }
            }
            int num=0;
            while(rear>0)
            {
                num+=l[rear-1];
                ans=max(ans,num*s[rear-1]);
                rear--;
            }

        }
    printf("%d\n",ans*3);
    }
    return 0;
}
这里写图片描述
这里写图片描述

哇塞,果然只要360ms。算法是多么神奇和巧妙,效率的差距也是立竿见影 其实这道题目并不难,用O(n^2)效率的算法足可以Ac掉三个OJ里的题目,但是我想做ACM,不应该AC了就满足了,你追求越高,要求越高,你的境界就越高。仔细钻研一个问题,真是很重要的事情。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016-02-24 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档