[FZOJ1565]&&[2014-10-23 模拟赛] 土豪聪要请客 (stol)

2014-10-24
竞赛题解 / 动态规划
FZOJ

描述 Description

众所周知，聪哥 (ndsf) 是个土豪，不过你们不知道的是他的 MZ 和他的 RMB 一样滴多……

某天土豪聪又赚了 10^10000e 的 RMB，他比较开心，于是准备请客。他在自己在 XX 星上的别墅里面大摆酒席，想要邀请尽可能多的 MZ 来参加他的宴会。他将会同 MZ 一起坐在一个巨大的长方形桌子上。这个桌子能坐下的人数等于他的边长。聪哥要求他的桌子能够放进他的别墅，并且桌子的边必须与别墅的边界平行。给定别墅的平面图，请你求出聪哥最多可以请多少个 MZ。

输入格式 InputFormat

第一行 n,m。表示别墅的长宽
下面 n 行，每行 M 个字符，表示一个方块是空的 (‘’) 或是被占用了(‘X’)。
聪哥只要他的桌子放在别墅里，并且桌子不能占用任何一个已经占用了的方块。

输出格式 OutputFormat

一个数，表示聪哥最多可以请几个 Maze。

样例输入 SampleInput

4 4
X.XX
X..X
..X.
..XX

样例输出 SampleOutput

9

FZOJ 1565

代码 Code

求周长最大的子矩阵。这里使用 O(n2)的算法，用 h[i]表示到当前行时，第 i 列的连续可行格的高度，fl[i]表示矩阵高度为 h[i]右端点为 i 时最远的左端点，同理 fr[i]表示最远的右端点。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
char a[405][405];
int h[405];
int fl[405],fr[405];
char ch;
int ans;
int main()
{
    scanf("%d%d\n",&n,&m);
    memset(h,sizeof(h),0);
    ans=0;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++) 
        {
            fl[j]=fr[j]=j;
            ch=getchar();
            if (ch=='.') h[j]++;
            else h[j]=0;
        }
        for (j=1;j<=m;j++)
        {
            while (h[j] && fl[j]>1 && h[j]<=h[fl[j]-1]) fl[j]=fl[fl[j]-1];
            while (h[m-j+1] && fr[m-j+1]<m && h[m-j+1]<=h[fr[m-j+1]+1]) fr[m-j+1]=fr[fr[m-j+1]+1];
        }
        for (j=1;j<=m;j++) if (h[j]) ans=max(ans,(h[j]+fr[j]-fl[j]+1)*2);
        scanf("\n");
    }
    printf("%d\n",ans-1);
    return 0;
}