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变成负无穷大，这样求解最大子矩阵和就可以得到答案

#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;
}