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