NOIP2014无线网络发射器选址

2018-10-16 16:34:37


题目大意

在一个 128*128 的矩阵中,每一个点都有一个值,让你选一点 (a,b),在(x-d,y-d)到(x+d,y+d)中的之和值最大,并求出使之最大的方案数

Solution

这题纯暴力就能过,直接每次扫描区域内的点

当然你也可以写个二维前缀和优化一下

纯暴力

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

struct wireless{
    int num=0;
}s[130][130];    //定义一个结构体存储每个坐标的值

int d,n;
long long sum=0,ans=0,num=0,z=0,x1,x2,y2,ya;

int main()
{
    cin>>d>>n;

    for(int i=0;i<n;i++)
    {
        int a,b,k;
        cin>>b>>a>>k; //a点和b点与二维数组的x,y相反要处理下 

        s[a][b].num=k; 
    }

    for(int i=0;i<=128;i++) //开始枚举
    {
        for(int j=0;j<=128;j++)
        {
            z=0; //先清空

            if(i-d<0) x1=0; //判断纵坐标起点
            else x1=i-d;    

            if(i+d>128) x2=128; //判断纵坐标终点
            else x2=i+d;    

            if(j-d<0) ya=0; //判断横坐标起点
            else ya=j-d;    

            if(j+d>128) y2=128; //判断横坐标终点
            else y2=j+d;

            for(int a=x1;a<=x2;a++)   //对公共场所数量累加
                for(int b=ya;b<=y2;b++)
                    z+=s[a][b].num; 

            if(z>sum) //如果大于前一个值则替换
            {
                sum=z;
                num=1;
            }
            else if(sum==z) //如何相等则数量相加
                    num++;
        }
    }

    cout<<num<<" "<<sum; //输出

    return 0;
}

二维前缀和优化

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int d,n,x,y,mem,maxx,tot;
int a[130][130];
int main()
{
    scanf("%d%d",&d,&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&y,&x,&mem);
        for(int j=max(x-d,0);j<=min(128,x+d);j++)
            for(int h=max(y-d,0);h<=min(128,y+d);h++)
            {
                a[j][h]+=mem;
                maxx=max(a[j][h],maxx);
            }
    }
    for(int j=0;j<=128;j++)
        for(int h=0;h<=128;h++)
        if(a[j][h]==maxx)
        tot++;
    printf("%d %d",tot,maxx);
}