NOIP2014无线网络发射器选址

题目大意 在一个 128*128 的矩阵中，每一个点都有一个值，让你选一点 (a,b)，在(x-d,y-d)到(x+d,y+d)中的之和值最大，并求出使之最大的方案数 Solution 这题纯暴力就能过，直接每次扫描区域内的点 当然你也可以写个二维前缀和优化一下 纯暴力 ```cpp #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; } ``` 二维前缀和优化 ```cpp #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); } ```