NC24156. [USACO 2015 Jan G]Cow Rectangles
描述
输入描述
The first line of input contains N. Each of the next N lines
describes a cow, and contains two integers and a character. The
integers indicate a point (x,y) (0 <= x, y <= 1000) at which the cow
is located. The character is H or G, indicating the cow's breed. No
two cows are located at the same point, and there is always at least
one Holstein.
输出描述
Print two integers. The first line should contain the maximum number
of Holsteins that can be enclosed by a fence containing no Guernseys,
and second line should contain the minimum area enclosed by such a
fence.
示例1
输入:
5 1 1 H 2 2 H 3 3 G 4 4 H 6 6 H
输出:
2 1
C++11(clang++ 3.9) 解法, 执行用时: 125ms, 内存消耗: 1376K, 提交时间: 2020-09-20 18:03:37
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
const int N=5e2+2;
struct pnt
{
int x,y,w;
pnt() {}
pnt(int x,int y) : x(x),y(y) {}
};
bool cmpx(pnt x,pnt y) {return x.x<y.x;}
bool cmpy(pnt x,pnt y) {return x.y<y.y;}
pnt cow[N];
int val[N][N];
int rx[N],ry[N];
int main()
{
memset(val,0,sizeof(val));
int n; scanf("%d",&n);
for (int i=1;i<=n;i++)
{
char w;
scanf("%d%d",&cow[i].x,&cow[i].y);
getchar(); w=getchar();
cow[i].w=w-'G'?1:-1001;
}
std::sort(cow+1,cow+1+n,cmpx);
for (int i=1,j=0,lst;i<=n;i++)
{
if (i==1 || lst!=cow[i].x) j++;
lst=cow[i].x;
rx[j]=cow[i].x;
cow[i].x=j;
}
int xb=cow[n].x;
std::sort(cow+1,cow+1+n,cmpy);
for (int i=1,j=0,lst;i<=n;i++)
{
if (i==1 || lst!=cow[i].y) j++;
lst=cow[i].y;
ry[j]=cow[i].y;
cow[i].y=j;
}
int yb=cow[n].y;
for (int i=1;i<=n;i++) val[cow[i].x][cow[i].y]=cow[i].w;
for (int i=1;i<=xb;i++)
for (int j=1;j<=yb;j++)
val[i][j]+=val[i-1][j];
int ans=0,ansy=0;
for (int i=1;i<=xb;i++)
for (int j=i;j<=xb;j++)
{
int sum=0;
for (int l=1,r=1;r<=yb;r++)
{
int dt=val[j][r]-val[i-1][r],ar=(rx[j]-rx[i])*(ry[r]-ry[l]);
if (r==1 && dt<=0)
{
sum=0;
while (val[j][r]-val[i-1][r]<=0)
l=++r;
r--;
}
sum+=dt;
if (sum>ans) ans=sum,ansy=ar;
else if (sum==ans && ansy>ar) ansy=ar;
if (dt<0)
{
sum=0;
while (val[j][r]-val[i-1][r]<=0)
l=++r;
r--;
}
}
}
printf("%d\n%d\n",ans,ansy);
return 0;
}