题解 P3135 【[USACO16JAN]堡哞Fort Moo】

违规用户名71524 · 2018-09-26 09:46:06 · 题解

这个题我好像用暴力把其他人的dp都干爆了？？ 现在速度排第一。。。。 先处理出每个点向上（up数组），向左（l数组）能延伸到的最远的点，然后枚举矩形的两条纵向的边，这样只要保证矩形上下两条边联通就好了，用处理的l数组判断即可。中间随便把一些不可能更优的状态剪掉，轻松ac。 φ(゜▽゜*)♪

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<vector>
#include<math.h>
#include<stack>
#include<map>
#include<queue>
#define eps 1e-9
using namespace std;
int n,m;
char mp[205][205];
int up[205][205],l[205][205];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",mp[i]+1);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(i==1)up[i][j]=1;
            else
            {
                if(mp[i-1][j]=='X')
                {
                    up[i][j]=i;
                }
                else
                {
                    up[i][j]=up[i-1][j];
                }
            }
            if(j==1)l[i][j]=1;
            else
            {
                if(mp[i][j-1]=='X')
                {
                    l[i][j]=j;
                }
                else
                {
                    l[i][j]=l[i][j-1];
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=j;mp[i][k]!='X'&&k<=m;k++)
            {
                if((k-j+1)*(i-max(up[i][j],up[i][k])+1)<=ans)continue;
                for(int p=max(up[i][j],up[i][k]);p<=i;p++)
                {
                    if(l[p][k]<=j)
                    {
                        //cout<<i<<' '<<j<<' '<<k<<' '<<p<<' '<<(i-p+1)*(k-j+1)<<endl;
                        ans=max(ans,(i-p+1)*(k-j+1));
                    }
                }
            }
        }
    }
    printf("%d",ans);
}