admin 管理员组

文章数量: 887031

操练

操练

问题描述

高老大有一个 N∗N 的广场，被均分成 N∗N 个格子。
其中某些格子种上了树。
为了维护世界的和平，为了贯彻和平与发展的原则，老大不得不开始操练部下了。
部下们必须站在广场中某没种上树个格子中，而且一个格子内不允许有两个人站着。
同时，为了显得整齐划一，部下们要维护一个方阵的阵型，也就是 N∗N 的广场内的一个 X∗Y 的矩形（该矩形的长和宽必须与广场的长和宽平行），每个格子上都必须有一个部下。
现在老大想知道，一次最多操练多少个部下？

输入

输入文件名为Training.in。
输入第一行两个正整数 N 和 M，代表广场的长和宽。
下接一个 N 行 M 列的字符矩阵，若第 I 行第 J 列为‘0’则代表该格子上有一颗树。

输出

输出文件名为Training.out。
输出一次最多能够操练的部下个数。

输入样例

2
11
11

输出样例

4

数据范围

对于 80% 的数据， N<=250 ；
对于 100% 的数据， N<=1000 。

Solution

悬线法

Code

#include <iostream>
#include <cstdio>#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y)) using namespace std;int n,ans;int map[1010][1010];
int up[1010][1010];
int le[1010][1010];
int ri[1010][1010];int main(){freopen("training.in","r",stdin);freopen("training.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%1d",&map[i][j]);for(int i=1;i<=n;i++)ri[0][i]=n,le[0][i]=1;for(int i=1;i<=n;i++){int t=1;for(int j=1;j<=n;j++){if(map[i][j])le[i][j]=t;else le[i][j]=1,t=j+1;}t=n;for(int j=n;j>=1;j--){if(map[i][j])ri[i][j]=t;else ri[i][j]=n,t=j-1;}for(int j=1;j<=n;j++)if(map[i][j]){up[i][j]=up[i-1][j]+1;le[i][j]=Max(le[i][j],le[i-1][j]);ri[i][j]=Min(ri[i][j],ri[i-1][j]);ans=Max(ans,(ri[i][j]-le[i][j]+1)*up[i][j]);}}printf("%d\n",ans);return 0;
}

本文标签： 操练

版权声明：本文标题：操练 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687550045h114812.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。