自动搬运

查看原文

来自洛谷，原作者为

	嗯。 **

搬运于2025-08-24 21:24:18，当前版本为作者最后更新于2018-08-01 19:51:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

作为标签党的我首先点开标签：贪心好有道理的样子

再来看数据范围坐标100以内，n<=300，数据好水的样子

于是我想枚举左上角和右下角的点，然后再加一遍循环，蠢里蠢气的交了上去，结果全T美滋滋。

于是冷静分析，这是100的5次方，肯定不能过啊。但是好像100的4次方能过哦，于是结合最大加权矩形的做法：首先用一个数组记录以（1，1）为左上角，（i，j）为右下角的矩形的权值和。

然后再来枚举左上角，右下角的坐标（100的4次方），通过东拼西凑，算出矩形的权值和，然后按相同操作算出除去边界的小矩形的权值，就是边界的值了（即边界上点的个数）

题目应该没有提高+这么难的。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,ans=0;
int a[101][101];
int main()
{
	scanf("%d",&n);
	for(register int i=1;i<=n;i++)
	{
	    int x,y;
	    scanf("%d%d",&x,&y);
	    a[x][y]+=1;//一个点就是一个1的权值
	}
	for(register int x=1;x<=100;x++)
	for(register int y=1;y<=100;y++)
	a[x][y]+=a[x-1][y]+a[x][y-1]-a[x-1][y-1];//记录以（1，1）为左上角，（x，y）为右下角的矩形的权值和
	for(register int i=1;i<=99;i++)
	for(register int j=1;j<=99;j++)
	for(register int x=i+1;x<=100;x++)
	for(register int y=j+1;y<=100;y++)
	{
	    int sum1=a[x][y]-a[x][j-1]-a[i-1][y]+a[i-1][j-1];//（大矩形的权值和）应该很好理解吧，不能理解的可以画个图感性理解，理性分析一下
	    int sum2=a[x-1][y-1]-a[x-1][j]-a[i][y-1]+a[i][j];//小矩形的权值和，同上
	    sum1-=sum2;//边界的值 边界上点的个数
	    ans=ans<sum1?sum1:ans;//和ans比较大小
	}
	printf("%d",ans);
	return 0;
}