题解 P2038 【无线网络发射器选址】
Whiteying
2017-10-31 21:38:14
典型的枚举,先建一个二维数组储存该路口公共场所的数量,然后从(0,0)到(128,128)一个一个的试
枚举从(xi,yi)出发所能覆盖的所有数量,只要不超过边界就循环下去
然后再减去多加的轴上的数
如果当前值比最大值大的话,就更新最大值,将方案数恢复成1
相等就增加方案数
总体来说这个题算是noip day2 t1中比较简单的一道题
易错点是边界判定和减去多加的数
下面是代码:
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int a[150][150],x,y,d,n;
long long sum,z,ans,num;//开long long防爆
int main()
{
cin>>d>>n;
for(int i=1;i<=n;i++)
{
cin>>y>>x>>z; //注意:x点和y点与二维数组的x,y相反
a[x][y]=z; //因此在给地图赋值时xy反着输入
} //但经过验证其实正着输入其实也没问题
for(int i=0;i<129;i++) //暴力枚举
for(int j=0;j<129;j++) //把每一个点都枚举一遍
{
sum=0; //sum每次都回复为0
for(int xi=i;xi>=0&&xi<=128&&abs(xi-i)<=d;xi++)//枚举从(xi,yi)的右下方
for(int yi=j;yi>=0&&yi<=128&&abs(yi-j)<=d;yi++)
sum+=a[xi][yi];
for(int xi=i;xi>=0&&xi<=128&&abs(xi-i)<=d;xi++)//枚举从(xi,yi)的左下方
for(int yi=j;yi>=0&&yi<=128&&abs(yi-j)<=d;yi--)
sum+=a[xi][yi];
for(int xi=i;xi>=0&&xi<=128&&abs(xi-i)<=d;xi--)//枚举从(xi,yi)的右上方
for(int yi=j;yi>=0&&yi<=128&&abs(yi-j)<=d;yi++)
sum+=a[xi][yi];
for(int xi=i;xi>=0&&xi<=128&&abs(xi-i)<=d;xi--)//枚举从(xi,yi)的左上方
for(int yi=j;yi>=0&&yi<=128&&abs(yi-j)<=d;yi--)
sum+=a[xi][yi];
int yi=j;
for(int xi=i;xi>=0&&xi<=128&&abs(xi-i)<=d;xi++)//减去多加的下轴
sum-=a[xi][yi];
for(int xi=i;xi>=0&&xi<=128&&abs(xi-i)<=d;xi--)//减去多加的上轴
sum-=a[xi][yi];
int xi=i;
for(int yi=j;yi>=0&&yi<=128&&abs(yi-j)<=d;yi++)//减去多加的右轴
sum-=a[xi][yi];
for(int yi=j;yi>=0&&yi<=128&&abs(yi-j)<=d;yi--)//减去多加的左轴
sum-=a[xi][yi];
sum+=a[i][j]; //加上当前点(xi,yi)
if(sum>ans)//如果当前值比最大值大的话
{
ans=sum;
num=1;
}
else if(sum==ans)//相等就增加方案数
num++;
}
cout<<num<<' '<<ans;//输入方案数和最大值
return 0;
}
```