1506意甲冠军：给你一个连续的直方图（拼贴底部长度1）。求连续基质区。

对每一个直方图，分别向左向右进行扩展。

#include<cstdio>

#include<stdlib.h>

#include<string.h>

#include<string>

#include<map>

#include<cmath>

#include<iostream>

#include <queue>

#include <stack>

#include<algorithm>

#include<set>

using namespace std;

#define INF 1e8

#define eps 1e-8

#define LL long long

#define N 100010

#define mol 1000000007

int i,n,t;

LL a[N],l[N],r[N],Max;

int main()

{

    while (scanf("%d",&n) &&  n)

    {

        for (i=1; i<=n; ++i) scanf("%I64d",&a[i]);

        l[1]=1;

        r[n]=n;

        for(i=2;i<=n;i++)

        {

            t=i;

            while(t>1&&a[i]<=a[t-1])//从左往右向左扩展

                t=l[t-1];

            l[i]=t;

        }

        for(i=n-1;i>=1;i--)

        {

            t=i;

            while(t<n&&a[i]<=a[t+1])//从右往左向右扩展

                t=r[t+1];

            r[i]=t;

        }

        Max=0;

        for (i=1; i<=n; ++i)

        {

            if ((r[i]-l[i]+1)*a[i]>Max)

                Max=(r[i]-l[i]+1)*a[i];

        }

        printf("%I64d\n",Max);

    }

    return 0;

}  

1505题意：求最大零（F）矩阵，1506加强版，把2维转换化成以每一行底,组成的最大面积

#include<cstdio>

#include<stdlib.h>

#include<string.h>

#include<string>

#include<map>

#include<cmath>

#include<iostream>

#include <queue>

#include <stack>

#include<algorithm>

#include<set>

using namespace std;

#define INF 1e8

#define eps 1e-8

#define LL long long

#define maxn 1001

#define mol 1000000007

int t,n,m,a[maxn][maxn],l[maxn][maxn],r[maxn][maxn];

char s[maxn];

int main()

{

	scanf("%d",&t);

	while(t--)

	{

		scanf("%d%d",&n,&m);

		int i,j;

		memset(a,0,sizeof(a));

		for(i=1;i<=n;i++)

		{

			for(j=1;j<=m;j++)

			{

				scanf("%s",s);

				if(s[0]=='F') a[i][j]=a[i-1][j]+1;

				else a[i][j]=0;

			}

		}

		//printf("\n");

		int ans=0;

		for(i=1;i<=n;i++)

		{

			int t;

			l[i][1]=1;r[i][m]=m;

			for(j=2;j<=m;j++)

			{

				t=j;

				while(t>1&&a[i][j]<=a[i][t-1])

					t=l[i][t-1];

				l[i][j]=t;

			}

			for(j=m-1;j>0;j--)

			{

				t=j;

				while(t<m&&a[i][j]<=a[i][t+1])

					t=r[i][t+1];

				r[i][j]=t;

			}

			for(j=1;j<=m;j++)

			{

				if(a[i][j]*(r[i][j]-l[i][j]+1)>ans)

					ans=a[i][j]*(r[i][j]-l[i][j]+1);

			}

		}

		printf("%d\n",ans*3);

	}

	return 0;

}

/*

2

5 6

R F F F F F

F F F F F F

R R R F F F

F F F F F F

F F F F F F

5 5

R R R R R

R R R R R

R R R R R

R R R R R

R R R R R

*/