题目描述

随着智能手机的日益普及，人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。

假设该城市的布局为由严格平行的129条东西向街道和129条南北向街道所形成的网格状，并且相邻的平行街道之间的距离都是恒定值1。东西向街道从北到南依次编号为0,1,2…128,南北向街道从西到东依次编号为0,1,2…128。

东西向街道和南北向街道相交形成路口，规定编号为x的南北向街道和编号为y的东西向街道形成的路口的坐标是（x, y）。 在某些路口存在一定数量的公共场所。

由于政府财政问题，只能安装一个大型无线网络发射器。该无线网络发射器的传播范围是一个以该点为中心，边长为2*d的正方形。传播范围包括正方形边界。

例如下图是一个d = 1的无线网络发射器的覆盖范围示意图。
   
现在政府有关部门准备安装一个传播参数为d的无线网络发射器，希望你帮助他们在城市内找出合适的安装地点，使得覆盖的公共场所最多。

输入描述:

第一行包含一个整数d，表示无线网络发射器的传播距离。
第二行包含一个整数n，表示有公共场所的路口数目。
接下来n行，每行给出三个整数x, y, k, 中间用一个空格隔开，分别代表路口的坐标(x,y)以及该路口公共场所的数量。同一坐标只会给出一次。

输出描述:

输出一行，包含两个整数，用一个空格隔开，分别表示能覆盖最多公共场所的安装地点方案数，以及能覆盖的最多公共场所的数量。

示例1

输入
1
2
4 4 10
6 6 20
输出
1 30

备注

对于100%的数据，1≤d≤20,1≤n≤20,0≤x≤128,0≤y≤128,0≤k≤1,000,000。

解答

这个题啊，其实是个大大大大大大暴力题。

本来代码的找方案数量部分用两重循环就可以了，然而为了省事我用了上面的代码改过来的（其实更麻烦，然而复制粘贴大法好= o =）。

有几个坑需要注意：如果这个WIFI发射器安在边上，也可能会达到最后方案的情况，所以要从最左边一排就开始枚举wifi放置点。所以为了防止数组越界，需要特判（然而我用了一个变量加了一下，这样就不会越界了。 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int a[180][180];
int c=20;//用上C是为了怕数组越界导致的RE，因为d的最大是20，所以就要20就够了
int n,k[180],d,x,y;//a数组是表示这个点有没有公共场所（或者是有几个），n是路口数目，d是发射器范围,x,y是坐标 
int ans=0,ans1=0;//ans是用来放最大的公共场所数，ans1是个临时变量，记下当一个wifi放置点有多少个公共场所 
int num=0;//记下有几个方案 
int main()
{
    scanf("%d",&d);
    scanf("%d",&n); 
    memset(a,0,sizeof(a));//先全部赋0，这样如果公共场所并没有的话直接不用操作 
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&k[i+c]);
        a[x+c][y+c]=k[i+c];
    }
    for(int i=c;i<=128+c;i++)
    {
        for(int j=c;j<=128+c;j++)//枚举整个路 
        {
            ans1=0;//需要在这里给ans1赋值，因为是找一个WIFI测试点就找一次ans1 
            for(int q=i-d;q<=i+d;q++)//枚举wifi放置点的范围 
            {
                for(int p=j-d;p<=j+d;p++)
                {
                    ans1+=a[q][p];
                    if(ans1>ans)
                    {
                        ans=ans1;
                    }
                }
            }
        }
    }
    for(int i=c;i<=128+c;i++)//第二次遍历，去找方案数量（其实这里可以用ans1搞一个数组来记录的，这样这半段的时间复杂度就会是N方，反正数据水，四次方就四次方吧） 
    {
        for(int j=c;j<=128+c;j++)//枚举整个路 
        {
            ans1=0; 
            for(int q=i-d;q<=i+d;q++)//枚举wifi放置点的范围 
            {
                for(int p=j-d;p<=j+d;p++)
                if(a[q][p]!=0)
                {
                    ans1+=a[q][p];
                    if(ans1==ans)//如果找到和最大覆盖数一样的方案，num++，由于是从头枚举，所以本来的最优方案数也会加进去，所以num开始赋0 
                    {
                        num++;
                    }
                }
            }
        }
    }
    printf("%d %d\n",num,ans);//记得有一个空格隔开 
    return 0;
}


来源：H2O3