[紫书][单调栈][思维] 求最大周长矩形 UVa12265

总感觉此题似曾相识，有很类似的求面积而非周长的题目？

题意给出长方形地图然后让求每个点对应的可贩卖的最大周长的矩形面积。考虑每一行的话，往上累计，然后就变成了一维的，在前面一些xx中求得最大/最小值的题，一般直接暴力会超时然后就用单调数据结构优化，这里左边每次动都相当于一个新的开始，所以就是添加和删除操作都在右侧进行，单调栈走起了。

#include 
#include
#include
using namespace std;

typedef long long LL;
const int maxn=1e3+5;
const int MOD=1e9+7;

char board[maxn][maxn];
int h[maxn][maxn];
int ans[maxn<<1];

int fuc(int i,int j){return h[i][j]-j;}

struct Rec
{
    int h,c;
    Rec(){h=0,c=0;}
    Rec(int h,int c):h(h),c(c){}
};

int top;//top of stack
Rec st[maxn];

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    int T,n,m;
    scanf("%d",&T);
    while(T--)
    {
        //memset(h,0,sizeof(h));
        memset(ans,0,sizeof(ans));
        scanf("%d%d",&n,&m);
        for (int i=1; i<=n; i++)
        {
            scanf(" %s",board[i]+1);
        }

        for (int i=1; i<=n; i++)
        {
            for (int j=1; j<=m; j++)
            {
                if(board[i][j]=='.')
                    h[i][j]=h[i-1][j]+1;
                else
                    h[i][j]=0;
            }
            //cout<-1&&r.h<=st[top].h)r.c=st[top--].c;//error1
                if(top==-1||r.h-r.c>st[top].h-st[top].c)st[++top]=r;
                ans[st[top].h-st[top].c+j+1]++;
            }
            else
                top=-1;//error2
        }
        for (int i=1;i<=m+n;i++)if(ans[i])
            printf("%d x %d\n",ans[i],2*i);
    }
    return 0;
}