HDU1505_City Game & HDU1506_Largest Rectangle in a Histogram（最大子矩阵和最大子矩形）

#include<stdio.h>
#include<string.h>
 
int l[100010],r[100010];
__int64 h[100010];
int main()
{
    int N;
    while(~scanf("%d",&N) && N!=0)
    {
        memset(h,0,sizeof(h));
        for(int i = 1; i <= N; i++)
        {
            scanf("%I64d",&h[i]);
            l[i] = r[i] = i;
        }
 
        l[0] = 1;
        r[N+1] = N;
        h[0] = -1;
        h[N+1] = -1;
        //这上边不加就会超时，不加的话下边就可能一直while，跳不出循环
        for(int i = 1; i <= N; i++)
        {
            while(h[l[i]-1] >= h[i])//找位置i的左边界
                l[i] = l[l[i]-1];
        }
        for(int i = N; i >= 1; i--)
        {
            while(h[r[i]+1] >= h[i])//找位置i的右边界
                r[i] = r[r[i]+1];
        }
        __int64 MaxArea = -0xffffff0;
        for(int i = 1; i <= N; i++)
        {
            if(h[i]*(r[i]-l[i]+1) > MaxArea)
                MaxArea = h[i]*(r[i]-l[i]+1);
        }
        printf("%I64d\n",MaxArea);
    }
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<fstream>
#include<algorithm>
using namespace std;

#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
//#define CLR(a) memset(a,0,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
const double eps=1e-6;
const int INF = 0x3f3f3f3f;
const int maxn = 1010;
int h[maxn][maxn];
int l[maxn];
int r[maxn];
char g[10];

int main(){
	int t;
	scanf("%d", &t);
	while(t--){
		int n,m;
		scanf("%d%d", &n,&m);
		rep(i,1,n){
			rep(j,1,m){
				scanf("%s", g);
				if(g[0]=='F')h[i][j] = h[i-1][j]+1;
				else h[i][j]=0;
			}
		}
		int maxx = -INF;
		rep(i,1,n){
			l[0]=1;
			r[m]=m;
			h[i][0]=-1;
			h[i][m+1]=-1;
			rep(j,1,m){
				l[j]=r[j]=j;
			}
			rep(j,1,m){
				while(h[i][l[j]-1]>=h[i][j]) l[j]=l[j]-1;
				while(h[i][r[j]+1]>=h[i][j]) r[j]=r[j]+1;
			}
			rep(j,1,m){
				maxx=max(maxx,h[i][j]*(r[j]-l[j]+1));
			}
		}
		printf("%d\n", maxx*3);
	}
	return 0;
}