题目大意
约翰的N(1 <= N <= 500)头奶牛的位置由坐标平面上的点来描述。这些奶牛分为两种：Holsteins 和 Guernseys。约翰想要修建一个矩形的围栏，围栏的边平行于x轴或者y轴，并且要求围栏中只有Holsteins类型的奶牛(一头奶牛在围栏的边边上也算在围栏以内)。
约翰想要使围栏围住进可能多的Holsteins奶牛，在此基础上，约翰希望围栏构成的矩形的面积尽可能小，请你计算出这个最小面积。
注意：围栏的长或宽为0的情况是允许的。
题目分析
一共有500头牛，但坐标为0~1000，所以先把每头牛的坐标离散。
对于这类矩阵问题，我们最开始的想法就是暴力。枚举矩阵的上界与下界，然后从左往右按列递推。若该列上没有G，则可以更新答案，否则将临时变量清零，继续递推。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int MAXN=505; 4 5 int n,m,ans1,ans2; 6 int nx,ny; 7 int px[MAXN],py[MAXN]; 8 int a[MAXN],b[MAXN]; 9 char bel[MAXN],tmp[5]; 10 int f[MAXN][MAXN],g[MAXN][MAXN]; 11 int main(){ 12 scanf("%d",&n); 13 for(int i=1;i<=n;++i){ 14 scanf("%d%d%s",&px[i],&py[i],tmp); 15 bel[i]=tmp[0]; 16 a[i]=px[i];b[i]=py[i]; 17 } 18 sort(a+1,a+n+1);sort(b+1,b+n+1); 19 nx=unique(a+1,a+n+1)-a-1; 20 ny=unique(b+1,b+n+1)-b-1; 21 for(int i=1;i<=n;++i){ 22 px[i]=lower_bound(a+1,a+nx+1,px[i])-a; 23 py[i]=lower_bound(b+1,b+ny+1,py[i])-b; 24 } 25 26 for(int i=1;i<=n;++i) 27 if(bel[i]=='H') 28 ++f[px[i]][py[i]]; 29 else 30 ++g[px[i]][py[i]]; 31 for(int i=1;i<=nx;++i) 32 for(int j=1;j<=ny;++j){ 33 f[i][j]+=f[i-1][j]; 34 g[i][j]+=g[i-1][j]; 35 } 36 for(int i=1;i<=nx;++i) 37 for(int j=i;j<=nx;++j){ 38 int l=1,r=1,res=0; 39 while(r<=ny){ 40 while(l<=ny&&(g[j][l]-g[i-1][l]||!(f[j][l]-f[i-1][l]))){ 41 ++l; 42 res-=f[j][l]-f[i-1][l]; 43 } 44 r=l;res=0; 45 while(!(g[j][r]-g[i-1][r])&&r<=ny){ 46 res+=f[j][r]-f[i-1][r]; 47 if(res>ans1){ 48 ans1=res; 49 ans2=(a[j]-a[i])*(b[r]-b[l]); 50 } 51 if(res==ans1) 52 ans2=min(ans2,(a[j]-a[i])*(b[r]-b[l])); 53 ++r; 54 } 55 l=r; 56 } 57 } 58 printf("%d %d ",ans1,ans2); 59 return 0; 60 }