专栏首页算法修养POJ 1964&HDU 1505&HOJ 1644 City Game(最大0,1子矩阵和总结)

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

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

#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

#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).

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

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

#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了就满足了,你追求越高,要求越高,你的境界就越高。仔细钻研一个问题,真是很重要的事情。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 天梯赛 大区赛 L3-014.周游世界 (Dijkstra)

    L3-014. 周游世界 时间限制 200 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standar...

    ShenduCC
  • LeetCode 1585 Check If String Is Transformable With Substring Sort Operations

    题意:一个只有0-9组成的字符串,每次选择任意一个子串,按照数字从小到大排序。问从源字符串能否经过若干次操作转换成目标字符串。

    ShenduCC
  • LeetCode Contest 180

    ShenduCC
  • 04:最长公共子上升序列

    总时间限制: 10000ms内存限制: 65536kB描述给定两个整数序列,写一个程序求它们的最长上升公共子序列。 当以下条件满足的时候,我们将长度为N的序列S...

    attack
  • HDU4576 Robot(概率)

    抄袭自https://www.cnblogs.com/Paul-Guderian/p/7624039.html

    attack
  • 洛谷P2765 魔术球问题(贪心 最大流)

    attack
  • P1018 乘积最大

    题目描述 今年是国际数学联盟确定的“2000――世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智...

    attack
  • P1903 【模板】分块/带修改莫队(数颜色)

    题目描述 墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到...

    attack
  • Day3上午解题报告

    预计分数:100+40+50=190 实际分数:100+40+50=190 T1 https://www.luogu.org/problem/show?pid=...

    attack
  • 1035. 插入与归并(25)

    插入排序是迭代算法,逐一获得输入数据,逐步产生有序的输出序列。每步迭代中,算法从输入序列中取出一元素,将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

    AI那点小事

扫码关注云+社区

领取腾讯云代金券