在一个 的城市网格中，需要部署无线网络信号塔来为居民区提供服务。网格中每个单元格的属性由一个整数值 定义： 1. 如果 0" ，表示该单元格是一个居民区，其数据需求为 。 2. 如果 ，表示该单元格可以建立一个信号塔，其信号半径为 。 3. 如果 ，表示该单元格是空地。 一个位于 的信号塔，其信号半径为 (即其原始值为 )，能够覆盖另一个位于 的居民区，当且仅当它们的欧几里得距离满足以下条件： - 未被任何信号塔覆盖的居民区，其数据服务价值为 0。 - 如果一个居民区被 个信号塔同时覆盖，由于信号干扰，其有效数据服务价值将从 下降为 。 你需要制定一个信号塔激活方案，选择激活哪些信号塔，以最大化所有居民区的总有效数据服务价值。请计算这个最大总价值，以及在达到最大总价值时，所需激活的最少信号塔数量。
输入描述:
第一行输入两个整数 和 ()，代表城市网格的尺寸。接下来 行，每行包含 个整数，代表网格单元格的属性值 ()。数据保证信号塔的总数（即 的单元格数量）不超过 11 个。
输出描述:
输出一行，包含两个用空格隔开的整数，分别代表：1. 可以实现的最大总数据服务价值。2. 在实现最大价值的前提下，所需激活的最少信号塔数量。
示例1
输入
12 10
0 500 0 0 0 0 0 0 0 0
73 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
-401 0 0 0 0 0 -431 0 0 0
381 0 0 0 0 0 0 0 66 0
0 269 0 0 -783 0 0 0 0 0
0 0 0 0 0 680 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 289 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 804 0 0 0 0 0
0 0 0 0 0 0 0 -579 0 0
备注:
本题由牛友@Charles 整理上传
加载中...