无线网络信号塔覆盖

题意

给一个 $m \times n$ 的城市网格，每个格子有一个整数值：

正数：居民区，数据需求为该值 $d$
负数：可以建信号塔的位置，信号半径为 $|v|$
零：空地

信号塔在 $(x_1, y_1)$ ，半径为 $r$ ，能覆盖 $(x_2, y_2)$ 处的居民区，条件是欧几里得距离 $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} \le r$ 。

服务价值规则：

没被任何塔覆盖的居民区，价值为 0
被 $k$ 个塔同时覆盖的居民区，有效价值从 $d$ 降为 $\lfloor d / k \rfloor$ （信号干扰）

目标：选择激活哪些塔，使总有效价值最大。在最大价值前提下，激活的塔数尽量少。

数据范围： $1 \le m, n \le 100$ ，信号塔数量不超过 11。

思路

看到"信号塔数量不超过 11"，这个限制非常关键。 $2^{11} = 2048$ ，直接枚举所有信号塔的激活方案完全可行。

先想清楚整个流程：

预处理覆盖关系

遍历网格，把所有塔和居民区分别收集出来。然后对于每个塔，算它能覆盖哪些居民区——判断欧几里得距离是否不超过半径即可。

这里有个小技巧：比较距离的时候不要开根号，直接比较距离的平方和半径的平方，既快又避免浮点误差。

枚举子集

用二进制掩码 $mask$ 从 0 到 $2^T - 1$ 枚举所有激活方案。对每个方案：

对每个居民区，数一下有多少个激活的塔覆盖了它（记为 $k$ ）
如果 $k > 0$ ，该居民区贡献 $\lfloor d / k \rfloor$
把所有居民区的贡献加起来就是总价值

维护全局最大价值和对应的最少塔数即可。

进一步优化

居民区数量可能很多（网格最大 $100 \times 100 = 10000$ ），但塔最多 11 个。对每个居民区预处理一个"哪些塔能覆盖它"的位掩码 $rcov[r]$ ，这样在枚举子集时， $rcov[r] \& mask$ 就能快速得到实际覆盖该居民区的塔集合，再用 popcount 数个数。

复杂度

预处理覆盖关系： $O(T \times R)$ ，其中 $T \le 11$ ， $R \le 10000$
枚举子集： $O(2^T \times R)$ ，最坏 $2048 \times 10000 \approx 2 \times 10^7$

完全没问题。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    int m, n;
    scanf("%d%d", &m, &n);
    vector<vector<int>> grid(m, vector<int>(n));
    vector<array<int,3>> towers, residents;
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++){
            scanf("%d", &grid[i][j]);
            if(grid[i][j] < 0) towers.push_back({i, j, -grid[i][j]});
            else if(grid[i][j] > 0) residents.push_back({i, j, grid[i][j]});
        }
    int T = towers.size();
    int R = residents.size();
    // cover[t][r] = 塔 t 是否覆盖居民区 r
    vector<vector<bool>> cover(T, vector<bool>(R, false));
    for(int t = 0; t < T; t++){
        int tx = towers[t][0], ty = towers[t][1];
        long long tr = towers[t][2];
        for(int r = 0; r < R; r++){
            int rx = residents[r][0], ry = residents[r][1];
            long long dx = tx - rx, dy = ty - ry;
            if(dx*dx + dy*dy <= tr*tr) cover[t][r] = true;
        }
    }
    long long bestVal = 0;
    int bestCnt = 0;
    for(int mask = 0; mask < (1 << T); mask++){
        int tc = __builtin_popcount(mask);
        long long val = 0;
        for(int r = 0; r < R; r++){
            int cnt = 0;
            for(int t = 0; t < T; t++){
                if((mask & (1 << t)) && cover[t][r]) cnt++;
            }
            if(cnt > 0) val += residents[r][2] / cnt;
        }
        if(val > bestVal || (val == bestVal && tc < bestCnt)){
            bestVal = val;
            bestCnt = tc;
        }
    }
    printf("%lld %d\n", bestVal, bestCnt);
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(), n = sc.nextInt();
        List<int[]> towers = new ArrayList<>();
        List<int[]> residents = new ArrayList<>();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                int v = sc.nextInt();
                if (v < 0) towers.add(new int[]{i, j, -v});
                else if (v > 0) residents.add(new int[]{i, j, v});
            }
        int T = towers.size(), R = residents.size();
        boolean[][] cover = new boolean[T][R];
        for (int t = 0; t < T; t++) {
            int tx = towers.get(t)[0], ty = towers.get(t)[1];
            long tr = towers.get(t)[2];
            for (int r = 0; r < R; r++) {
                int rx = residents.get(r)[0], ry = residents.get(r)[1];
                long dx = tx - rx, dy = ty - ry;
                if (dx * dx + dy * dy <= tr * tr) cover[t][r] = true;
            }
        }
        long bestVal = 0;
        int bestCnt = 0;
        for (int mask = 0; mask < (1 << T); mask++) {
            int tc = Integer.bitCount(mask);
            long val = 0;
            for (int r = 0; r < R; r++) {
                int cnt = 0;
                for (int t = 0; t < T; t++)
                    if ((mask & (1 << t)) != 0 && cover[t][r]) cnt++;
                if (cnt > 0) val += residents.get(r)[2] / cnt;
            }
            if (val > bestVal || (val == bestVal && tc < bestCnt)) {
                bestVal = val;
                bestCnt = tc;
            }
        }
        System.out.println(bestVal + " " + bestCnt);
    }
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    m = int(data[idx]); idx += 1
    n = int(data[idx]); idx += 1
    towers = []
    residents = []
    for i in range(m):
        for j in range(n):
            v = int(data[idx]); idx += 1
            if v < 0:
                towers.append((i, j, -v))
            elif v > 0:
                residents.append((i, j, v))
    T = len(towers)
    R = len(residents)
    # 对每个居民区，预处理能覆盖它的塔的位掩码
    rcov = [0] * R
    for t in range(T):
        tx, ty, tr = towers[t]
        tr2 = tr * tr
        for r in range(R):
            rx, ry, rd = residents[r]
            dx, dy = tx - rx, ty - ry
            if dx*dx + dy*dy <= tr2:
                rcov[r] |= (1 << t)
    best_val = 0
    best_cnt = 0
    for mask in range(1 << T):
        tc = bin(mask).count('1')
        val = 0
        for r in range(R):
            active = rcov[r] & mask
            if active:
                cnt = bin(active).count('1')
                val += residents[r][2] // cnt
        if val > best_val or (val == best_val and tc < best_cnt):
            best_val = val
            best_cnt = tc
    print(best_val, best_cnt)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l.trim()));
rl.on('close', () => {
    let idx = 0;
    const [m, n] = lines[idx++].split(' ').map(Number);
    const towers = [], residents = [];
    for (let i = 0; i < m; i++) {
        const row = lines[idx++].split(/\s+/).map(Number);
        for (let j = 0; j < n; j++) {
            if (row[j] < 0) towers.push([i, j, -row[j]]);
            else if (row[j] > 0) residents.push([i, j, row[j]]);
        }
    }
    const T = towers.length, R = residents.length;
    const cover = Array.from({length: T}, () => Array(R).fill(false));
    for (let t = 0; t < T; t++) {
        const [tx, ty, tr] = towers[t];
        for (let r = 0; r < R; r++) {
            const dx = tx - residents[r][0], dy = ty - residents[r][1];
            if (dx*dx + dy*dy <= tr*tr) cover[t][r] = true;
        }
    }
    let bestVal = 0, bestCnt = 0;
    for (let mask = 0; mask < (1 << T); mask++) {
        let tc = 0;
        for (let b = mask; b; b &= b-1) tc++;
        let val = 0;
        for (let r = 0; r < R; r++) {
            let cnt = 0;
            for (let t = 0; t < T; t++)
                if ((mask & (1 << t)) && cover[t][r]) cnt++;
            if (cnt > 0) val += Math.floor(residents[r][2] / cnt);
        }
        if (val > bestVal || (val === bestVal && tc < bestCnt)) {
            bestVal = val;
            bestCnt = tc;
        }
    }
    console.log(bestVal + ' ' + bestCnt);
});