uva 12265 贩卖土地

题目大意：

有一个矩阵有些点可以取有些不能

求以每个点为右下角的子矩阵（里面点都可以取）的周长最大值

最后统计出每个周长对应矩阵的个数

思路：

单调栈

先预处理出每个点向上最多能延伸多长记为h（i，j）

然后对于每行维护一个单调栈记录每行最远可以达到的左端点和该矩形的高

该单调栈满足高单调递增

每次加入一个元素时，判断新增加的高度是否比减去的长度多

若是，就加入栈，反之不入栈

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 #include<vector>

 #define ll long long

 #define inf 2147483611

 #define MAXN 1010

 #define MOD

 using namespace std;

 inline int read()

 {

     int x=,f=;

     char ch;ch=getchar();

     while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}

     while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int pos,top,T,n,m,ans[MAXN*],h[MAXN][MAXN];

 char map[MAXN];

 struct data

 {

     int x,y;

 }s[MAXN];

 int main()

 {

     T=read();

     while(T--)

     {

         n=read(),m=read();

         memset(h,,sizeof(h));

         memset(ans,,sizeof(ans));

         for(int i=;i<=n;i++)

         {

             scanf("%s",map+);

             for(int j=;j<=m;j++)

                 if(map[j]=='.') h[i][j]=h[i-][j]+;

         }

         for(int i=;i<=n;i++)

         {

             memset(s,,sizeof(s));top=;

             for(int j=;j<=m;j++)

             {

                 pos=j;

                 while(top&&s[top].y>=h[i][j]) {pos=s[top].x;top--;}

                 if(!h[i][j]) continue;

                 if(!top||h[i][j]-s[top].y>pos-s[top].x)

                 {

                     ans[h[i][j]+j-pos+]++;

                     data tmp;tmp.x=pos,tmp.y=h[i][j];

                     s[++top]=tmp;

                 }

                 else ans[s[top].y+j-s[top].x+]++;

             }

         }

         for(int i=;i<=n+m;i++)

         {

             if(ans[i]) printf("%d x %d\n",ans[i],i*);

         }

     }

 }

巴特西

uva 12265 贩卖土地

最新文章

热门文章