解题思路

• 网格大小为 n*m。

  • a[i][j] > 0：价值为 a[i][j] 的作物；
  • a[i][j] = 0：空地；
  • a[i][j] < 0：半径为 -a[i][j] 的洒灌器（欧氏距离，含边界）。

• 若一个作物格被激活的洒灌器覆盖了 k ≥ 1 次，价值变为 v/k；未覆盖则价值为 0。目标：选择要开启的洒灌器，使总价值最大；若最大价值有多解，洒灌器开启数量取最小。输出总价值的整数部分（向下取整）及最少开启数量。

核心算法

1. 洒灌器数量上限小：题面给出洒灌器总数 irr_num ≤ 11。 因此可对洒灌器集合进行子集枚举（至多 2^11 = 2048 个子集）。

2. 覆盖掩码聚合：

   • 先枚举每个作物格，计算它被哪些洒灌器覆盖，得到一个长度为 irr_num 的位掩码 mask（第 t 位为 1 表示第 t 个洒灌器覆盖该格）。
   • 将所有作物按 mask 聚合，记 sum[mask] 为该类作物原始价值之和（mask=0 无法被任何洒灌器覆盖，可忽略）。

3. 评估每个开启方案：

   • 对每个子集 S（表示开启的洒灌器），总价值

   

   • 取 f(S) 最大的方案；若多个方案达到同一最大值（以微小 eps 判等），取 |S|（开启数量）最小的。

4. 实现要点

   • 计算覆盖采用欧氏距离平方比较：(x1-x2)^2 + (y1-y2)^2 <= r^2。
   • 为避免重复扫描整图：只对 a[i][j]>0 的格子计算其覆盖 mask。
   • 评估阶段只遍历出现过的 mask（sum[mask]>0）。
   • 浮点误差处理：比较时使用 eps = 1e-9，最终对最大价值做 floor（或 int(ans+1e-9)）。

复杂度分析

• 设洒灌器数量为 k (≤11)，网格大小 N=n*m (≤ 360000)。
• 预处理（给每个作物求覆盖掩码）：O(N * k)（最多约 4e6 次简单运算）
• 枚举方案并计算总价值：O(2^k * M)，其中 M ≤ 2^k-1 为出现过的掩码数量。最坏 O(4^k)，k≤11 时约 420 万次，足够快。
• 额外空间：O(2^k) 存储 sum[mask]。

代码实现

Python

# -*- coding: utf-8 -*-
import sys
from math import floor

EPS = 1e-9

def calc_best_value(n, m, a):
    sprinklers = []  # (x, y, r)
    for i in range(n):
        for j in range(m):
            if a[i][j] < 0:
                sprinklers.append((i, j, -a[i][j]))
    k = len(sprinklers)
    if k == 0:
        return 0, 0  # 没有洒灌器，价值为0，打开数量为0

    # 预聚合：sum[mask] 为被 mask 覆盖模式的作物价值之和
    sums = [0.0] * (1 << k)
    for i in range(n):
        for j in range(m):
            v = a[i][j]
            if v > 0:
                mask = 0
                # 计算该作物的覆盖掩码
                for t, (x, y, r) in enumerate(sprinklers):
                    dx = i - x
                    dy = j - y
                    if dx * dx + dy * dy <= r * r:
                        mask |= (1 << t)
                if mask != 0:
                    sums[mask] += v

    best_val = 0.0
    best_cnt = 0

    # 子集枚举：S 表示打开的洒灌器集合
    for S in range(1 << k):
        total = 0.0
        if S != 0:
            for mask in range(1, 1 << k):
                sv = sums[mask]
                if sv == 0.0:
                    continue
                inter = mask & S
                if inter != 0:
                    c = inter.bit_count()
                    total += sv / c
        # 比较并记录答案（tie 时开启数量更小）
        cnt = S.bit_count()
        if total > best_val + EPS or (abs(total - best_val) <= EPS and cnt < best_cnt):
            best_val, best_cnt = total, cnt

    return int(best_val + EPS), best_cnt

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        return
    it = iter(data)
    n = next(it); m = next(it)
    a = [[0]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            a[i][j] = next(it)
    val, used = calc_best_value(n, m, a)
    print(val, used)

if __name__ == "__main__":
    main()

Java

// -*- coding: utf-8 -*-
// ACM 风格，主类名 Main
import java.io.*;
import java.util.*;

public class Main {
    static final double EPS = 1e-9;

    // 计算答案的外部函数
    static long[] solve(int n, int m, int[][] a) {
        List<int[]> spr = new ArrayList<>(); // (x,y,r)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] < 0) spr.add(new int[]{i, j, -a[i][j]});
            }
        }
        int k = spr.size();
        if (k == 0) return new long[]{0L, 0L};

        double[] sums = new double[1 << k]; // sum[mask]

        // 仅遍历作物格，计算覆盖掩码
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int v = a[i][j];
                if (v > 0) {
                    int mask = 0;
                    for (int t = 0; t < k; t++) {
                        int[] s = spr.get(t);
                        int dx = i - s[0];
                        int dy = j - s[1];
                        int r = s[2];
                        if ((long)dx * dx + (long)dy * dy <= (long)r * r) {
                            mask |= (1 << t);
                        }
                    }
                    if (mask != 0) sums[mask] += v;
                }
            }
        }

        double bestVal = 0.0;
        int bestCnt = 0;

        // 枚举所有开启方案
        int lim = 1 << k;
        for (int S = 0; S < lim; S++) {
            double total = 0.0;
            if (S != 0) {
                for (int mask = 1; mask < lim; mask++) {
                    double sv = sums[mask];
                    if (sv == 0.0) continue;
                    int inter = mask & S;
                    if (inter != 0) {
                        int c = Integer.bitCount(inter);
                        total += sv / c;
                    }
                }
            }
            int cnt = Integer.bitCount(S);
            if (total > bestVal + EPS || (Math.abs(total - bestVal) <= EPS && cnt < bestCnt)) {
                bestVal = total;
                bestCnt = cnt;
            }
        }
        long valInt = (long) Math.floor(bestVal + EPS);
        return new long[]{valInt, bestCnt};
    }

    // 读入与输出在主函数中
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        long[] ans = solve(n, m, a);
        System.out.println(ans[0] + " " + ans[1]);
    }
}

C++

// -*- coding: utf-8 -*-
// ACM 风格：主函数读写，功能在外部函数 solve 中
#include <bits/stdc++.h>
using namespace std;

const long double EPS = 1e-9L;

pair<long long,int> solve(int n, int m, const vector<vector<int>>& a){
    struct S {int x,y,r;};
    vector<S> spr;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(a[i][j] < 0) spr.push_back({i,j,-a[i][j]});
    int k = (int)spr.size();
    if(k==0) return {0LL, 0};

    int LIM = 1<<k;
    vector<long double> sums(LIM, 0.0L); // sum[mask]

    // 仅对作物格计算覆盖掩码
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int v = a[i][j];
            if(v>0){
                int mask = 0;
                for(int t=0;t<k;t++){
                    long long dx = i - spr[t].x;
                    long long dy = j - spr[t].y;
                    long long rr = spr[t].r;
                    if(dx*dx + dy*dy <= rr*rr) mask |= (1<<t);
                }
                if(mask) sums[mask] += (long double)v;
            }
        }
    }

    long double bestVal = 0.0L;
    int bestCnt = 0;

    for(int S=0; S<LIM; S++){
        long double total = 0.0L;
        if(S!=0){
            for(int mask=1; mask<LIM; mask++){
                if(sums[mask]==0.0L) continue;
                int inter = mask & S;
                if(inter){
                    int c = __builtin_popcount((unsigned)inter);
                    total += sums[mask] / (long double)c;
                }
            }
        }
        int cnt = __builtin_popcount((unsigned)S);
        if(total > bestVal + EPS || (fabsl(total - bestVal) <= EPS && cnt < bestCnt)){
            bestVal = total;
            bestCnt = cnt;
        }
    }
    long long valInt = (long long)floor(bestVal + EPS);
    return {valInt, bestCnt};
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    if(!(cin>>n>>m)) return 0;
    vector<vector<int>> a(n, vector<int>(m));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>a[i][j];

    auto ans = solve(n,m,a);
    cout<<ans.first<<" "<<ans.second<<"\n";
    return 0;
}

题目内容

有一片 $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$