題目描述

隨著智能手機的日益普及，人們對無線網的需求日益增大。某城市決定對城市內的公共場所覆蓋無線網。

假設該城市的布局為由嚴格平行的?129?條東西向街道和?129?條南北向街道所形成的網格狀，并且相鄰的平行街道之間的距離都是恒定值?11?。

東西向街道從北到南依次編號為?0,1,2 ……1280?，南北向街道從西到東依次編號為?0,1,2 …… 1280?。

東西向街道和南北向街道相交形成路口，規定編號為?x?的南北向街道和編號為?y?的東西向街道形成的路口的坐標是?(x,y)?。

在某些路口存在一定數量的公共場所。

由于政府財政問題，只能安裝一個大型無線網絡發射器。該無線網絡發射器的傳播范圍是一個以該點為中心，邊長為?2d?的正方形。

傳播范圍包括正方形邊界。

現在政府有關部門準備安裝一個傳播參數為?d?的無線網絡發射器，希望你幫助他們在城市內找出合適的路口作為安裝地點，

使得覆蓋的公共場所最多。

輸入輸出格式

輸入格式：

?

第一行包含一個整數?d?，表示無線網絡發射器的傳播距離。

第二行包含一個整數?n?，表示有公共場所的路口數目。

接下來?n?行，每行給出三個整數?x, y, k，中間用一個空格隔開，分別代表路口的坐標?(x,y)?以及該路口公共場所的數量。同一坐標只會給出一次。

?

輸出格式：

?

輸出一行，包含兩個整數，用一個空格隔開，分別表示能覆蓋最多公共場所的安裝地點方案數，以及能覆蓋的最多公共場所的數量。

?

輸入輸出樣例

輸入樣例#1：?復制 1 2 4 4 10 6 6 20 輸出樣例#1：?復制 1 30

說明

對于100%的數據，1≤d≤20,1≤n≤20,0≤x≤128,0≤y≤128,0<k≤1000000

?

emm，說實話，，

不會做，

代碼也沒看懂，

dalao說什么前綴和，，很暈，

給你們看他的代碼吧：

?

1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 6 int d,n,x,y,bound,ans_max,ans_tot; 7 int sum[150][150]; 8 9 int main() 10 { 11 scanf("%d%d",&d,&n); 12 for(int i=1; i<=n; ++i) //把0~128移到1~129，方便算前綴和 13 { 14 scanf("%d%d",&x,&y); 15 scanf("%d",&sum[x+1][y+1]);//通過坐標+1實現 16 } 17 for(int i=1; i<=129+d; i++) //算前綴和 注意要加d，因為枚舉中心，如果位置很靠近邊界，范圍會超過129 18 for(int j=1; j<=129+d; j++) 19 sum[i][j]+=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]; 20 for(int i=1,a; i<=129; i++) 21 { 22 for(int j=1; j<=129; j++) 23 { 24 a=sum[i+d][j+d]-sum[i+d][max(0,j-d-1)]-sum[max(0,i-d-1)][j+d]+sum[max(0,i-d-1)][max(0,j-d-1)];//以它為中心，邊長為2n的正方形的前綴和 注意邊界不要<0 25 if(ans_max<a) //更新答案 26 { 27 ans_max=a; 28 ans_tot=1; 29 } 30 else if(ans_max==a) 31 ans_tot++; 32 } 33 } 34 printf("%d %d\n",ans_tot,ans_max); 35 return 0; 36 }

?

---

如果你不開心，那我就把右邊這個帥傻子分享給你吧，
你看，他這么好看，跟個zz一樣看著你，你還傷心嗎？
真的！這照片盯上他五秒鐘就想笑了。
一切都會過去的。
時間時間會給你答案2333

轉載于:https://www.cnblogs.com/Mary-Sue/p/9414100.html

總結

以上是生活随笔為你收集整理的P2038 无线网络发射器选址的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。