hdu 1505 City Game

预处理h[i][j] 表示i j 位置向上最多到哪

l r表示向左向右。。

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64
using namespace std;

int h[1010][1010],r[1010][1010],l[1010][1010];

int main()
{
    char s[5];
    int t,i,j,ans,n,m;
    scanf("%d",&t);
    while(t--)
    {
        memset(h,0,sizeof h);
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%s",s);
                if(s[0]==‘F‘) h[i][j]=h[i-1][j]+1;
            }
        ans=-1;
        for(i=1;i<=n;i++)
        {
            h[i][0]=h[i][m+1]=-1;//这里要改成-1啊。。
            for(j=1;j<=m;j++)
                l[i][j]=r[i][j]=j;
            for(j=2;j<=m;j++)
            {
                while(h[i][l[i][j]-1]>=h[i][j])
                    l[i][j]=l[i][l[i][j]-1];
            }
            for(j=m-1;j>0;j--)
            {
                while(h[i][r[i][j]+1]>=h[i][j])
                    r[i][j]=r[i][r[i][j]+1];
            }
            for(j=1;j<=m;j++)
            {
                if(h[i][j]*(r[i][j]-l[i][j]+1)>ans)
                    ans=h[i][j]*(r[i][j]-l[i][j]+1);
            }
        }
        printf("%d\n",ans*3);
    }
    return 0;
}

hdu 1505 City Game

原文：http://blog.csdn.net/u011032846/article/details/19016659