P3846.第3题-灌溉农场
题目内容
有一片 n∗m 大小的网格农场需要灌溉，每个格子中的数值 V[i][j] 表示为：
1、如果 V[i][j] 大于 0，代表该格子中为价值为 V 的经济作物;
2、如果 V[i][j] 小于 0 ，代表该格子中为浇灌半径为 −V 的浇灌器;
3、如果 V[i][j] 等于 0 ，代表该格子为空地;
假设位置 x1、y1 为一个浇灌器，其浇灌半径为 V ，对于其周围的作物 x2、y2 而言，当满足当 (x1−x2)2+(y1−y2)2<=(V[x1][y1])2 时，视为该方格能被灌溉器完全覆盖
如果作物 (i、j 位置处)未被灌溉器覆盖，则无法收获提供价值，如果某个方格被 k 个灌溉器覆盖，当 k 越大时则会使其因过度灌溉而导致价值下降为 V[i][j]/k ;
现在需要合理选择需要打开哪些浇灌器，使得作物价值最大化;
请计算总价值最大是多少(价值只输出整数部分，即向下取整)?
总价值最大时最少需要打开多少个浇灌器?
输入描述
第一行两个整数 n 和 m(1<=n,m<=600),表示大小为 n 行 m 列的网格农场。
接下来为 n 行，每行 m 个元素，第 i 行 j 列为 a[i][j],(−800<=a[i][j]<=1000) ,
当 a[i][j]>0 时表示有价值 a[i][j] 的经济作物，
当 a[i][j]=0 时表示为空地，
当 a[i][j]<0 时表示为喷射半径为 −a[i][j] 的浇灌器。
其中浇灌器的总数(即 a[i][j]<0 的格子数)记为 irr_num(0<=11)。
输出描述
输出使用空格分开的两个整数 val 和 used_num，表示能获得的最大总价值和总价值最大时最少需要打开的浇灌器数量。
总价值只需要输出整数部分即可。
样例1
输入
3 3
11 2 10
1 -1 15
12 2 0
输出
20 1
说明
浇灌器位于 (2,2) 位置处，位置 (1,1) 处的作物不满足 (2−1)2+(2−1)2<=1，所以无法浇灌到，位置 (1,2) 处的作物满足 (1−1)2+(2−1)2<=1，所以可以浇灌到；
同理，可以计算出，满足浇灌条件的作物分别位于 (1,2)、(2,1)、(2,3) 和 (3,2) 共四处；
这四处作物的经济价值分别为：2、1、15 和 2 ，总价值为 20 ；
所以输出为：20 1 ；
表示总价值为 20，使用一个浇灌器；
样例2
输入
3 5
11 2 10 1 3
1 -1 15 -1 1
12 2 23 8 2
输出
25 1
说明
该用例中，共有两个浇灌器，有三种组合方法，分别解释如下：
1、如果打开所有浇灌器：
(2,2) 位置的浇灌器可以覆盖 (1,2)(2,1)(2,3)(3,2) 一共四个作物
(2,4) 处的浇灌器可以覆盖 (1,4)(2,3)(2,5)(3,4) 一共四个作物
其中 (2,3) 位置处的作物被覆盖了两次，价值降低为 15/2=7 (向下取整)
最后总价值为 22 ；
2、如果只打开位置 (2,2) 处的浇灌器，可以覆盖 (1,2)(2,1)(2,3)(3,2) 一共四个作物；
总价值为 20 ；
3、如果只打开 (2,4) 处的浇灌器，可以覆盖 (1,4)(2,3)(2,5)(3,4) 一共四个作物；总价值为 25 ；
25>22>20 ：因此选择第三种方法，即：只打开 (2,4) 位置处的浇灌器即可，总价值为 25 ；
所以输出为：25 1
样例3
输入
4 5
11 2 10 1 3
1 -1 7 33 1
12 19 23 8 2
1 -1 0 31 7
输出
29 1
说明
该用例中，共有两个浇灌器，有三种组合方法，分别解释如下：
1、如果打开所有浇灌器：
(2,2) 位置的浇灌器可以覆盖 (1,2)(2,1)(2,3)(3,2) 一共四个作物
(4.2) 处的浇灌器可以覆盖 (3,2)(4,1) 一共两个作物
其中 (3,2) 位置处的作物被覆盖了两次，价值降低为 19/2=9 (向下取整)
最后总价值为 29 ；
2、如果只打开位置 (2,2) 处的浇灌器，可以覆盖 (1,2)(2,1)(2,3)(3,2) 一共四个作物；
总价值为 29；
3、如果只打开 (4,2) 处的浇灌器，可以覆盖 (3,2)(4,1)(4,3) 一共两个作物；
总价值为 20 ；
29==29>20 ； 当总价值相同的时候，选择使用浇灌器更少的方法，因此选择第二种方法，即：只打开 (2,2) 位置处的浇灌器即可，总价值为 29 ；
所以输出为：29 1
