题解 P1369 【矩形】

· · 题解

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

再来看数据范围坐标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;
}