题解 P2038 【无线网络发射器选址】

Whiteying

2017-10-31 21:38:14

Solution

典型的枚举,先建一个二维数组储存该路口公共场所的数量,然后从(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; } ```