解题思路

把 n×n 的网格按列看：一次“优化操作”会把某一整列标记为“强化覆盖”。 最后统计规则：未被选中的列，只要与其相邻（左或右）有被选中的列，则这一整列所有格子的数值都会计入总效益；被选中的列本身不计入。

因此，可把每一列的权值设为该列元素之和 w[j] = Σ_i grid[i][j]。问题转化为：

在长度为 n 的路径图（1…n）上，选择若干个点 S，使得未被选中的且与 S 相邻的点的权值和最大。 （被选中的点自身不计入。）

这可以用线性动态规划（DP） 解决。按列从左到右处理，维护列 j 的三种状态：

• state0：第 j 列未选，且目前还未被左边支配（左边没有选中列）；
• state1：第 j 列未选，且已被左边支配（左边紧挨的列已选中），此时它的权值 w[j] 已经加入总效益；
• state2：第 j 列已选。

转移（设上一列的 DP 为 dp0, dp1, dp2，当前列权值为 w[j]，上一列权值为 w[j-1]）：

• 选中第 j 列： 若上一列处于 state0（未被支配），此时会把上一列“补支配”，一次性增加 w[j-1]； 上一列为 state1/2 则不增加。 new2 = max(dp2, dp1, dp0 + w[j-1])（j=1 时没有上一列，增量视为 0）

• 不选第 j 列：

  • 若上一列为 state2（已选），则当前列被左侧支配，立即计入 w[j]：new1 = dp2 + w[j]
  • 否则当前列仍未被支配：new0 = max(dp0, dp1)

初始化：处理前 dp0=0, dp1=-∞, dp2=-∞。 答案为处理到第 n 列后的 max(new0, new1, new2)。

该 DP 在第一次被支配时就把该列权值加入，确保不会重复计数；被两侧同时支配也只加一次。

复杂度分析

• 先按列求和：O(n^2)
• 单次线性 DP：O(n)，仅常数状态
• 总时间复杂度：O(n^2)，空间复杂度：O(1)（不计输入与列和）

在 n ≤ 100 且元素非负的条件下，复杂度充足。

代码实现

Python

INF = 10 ** 18

def max_benefit(grid):
    n = len(grid)
    # 统计每一列的权值
    w = [0] * n
    for i in range(n):
        for j in range(n):
            w[j] += grid[i][j]

    # 动态规划，三种状态
    dp0, dp1, dp2 = 0, -INF, -INF  # 未选未支配 / 未选已支配 / 已选
    for j in range(n):
        add_prev = w[j - 1] if j > 0 else 0

        # 不选当前列
        new0 = max(dp0, dp1)          # 当前仍未被支配
        new1 = dp2 + w[j]             # 被左侧（上一列选中）支配，计入 w[j]

        # 选中当前列
        new2 = max(dp2, dp1, dp0 + add_prev)  # 若上一列未支配，则补上 w[j-1]

        dp0, dp1, dp2 = new0, new1, new2

    return max(dp0, dp1, dp2)

def main():
    n = int(input())
    grid = []
    for i in range(n):
        grid.append(list(map(int,input().split())))
    print(max_benefit(grid))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

/** ACM 风格主类 */
public class Main {

    // 计算最大总效益
    static long solve(int[][] grid) {
        int n = grid.length;
        long[] w = new long[n];
        // 按列求和
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) w[j] += grid[i][j];
        }

        long INF = (long)1e18;
        long dp0 = 0, dp1 = -INF, dp2 = -INF; // 未选未支配 / 未选已支配 / 已选

        for (int j = 0; j < n; j++) {
            long addPrev = (j > 0) ? w[j - 1] : 0;

            long new0 = Math.max(dp0, dp1);     // 当前不选，且未被左侧支配
            long new1 = dp2 + w[j];             // 当前不选，被左侧支配，计入 w[j]
            long new2 = Math.max(Math.max(dp2, dp1), dp0 + addPrev); // 选当前，补支配上一列

            dp0 = new0; dp1 = new1; dp2 = new2;
        }
        return Math.max(dp0, Math.max(dp1, dp2));
    }

    // 读取输入
    static int[][] readGrid(BufferedReader br) throws Exception {
        int n = Integer.parseInt(br.readLine().trim());
        int[][] grid = new int[n][n];
        for (int i = 0; i < n; i++) {
            String line = br.readLine().trim();
            String[] parts = line.split("\\s+");
            if (parts.length == n) {
                for (int j = 0; j < n; j++) grid[i][j] = Integer.parseInt(parts[j]);
            } else {
                // 无空格，则按字符读取（样例形式）
                for (int j = 0; j < n; j++) grid[i][j] = line.charAt(j) - '0';
            }
        }
        return grid;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] grid = readGrid(br);
        System.out.println(solve(grid));
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = (long long)1e18;

// 求最大总效益：列和 + 线性DP（三状态）
long long maxBenefit(const vector<vector<long long>>& grid) {
    int n = (int)grid.size();
    vector<long long> w(n, 0);
    // 按列求和
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            w[j] += grid[i][j];

    long long dp0 = 0, dp1 = -INF, dp2 = -INF; // 未选未支配 / 未选已支配 / 已选
    for (int j = 0; j < n; ++j) {
        long long addPrev = (j > 0) ? w[j - 1] : 0;

        long long new0 = max(dp0, dp1);           // 当前不选，未被左侧支配
        long long new1 = dp2 + w[j];              // 当前不选，被左侧支配（加入 w[j]）
        long long new2 = max({dp2, dp1, dp0 + addPrev}); // 当前选，补支配上一列

        dp0 = new0; dp1 = new1; dp2 = new2;
    }
    return max({dp0, dp1, dp2});
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<vector<long long>> grid(n, vector<long long>(n, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) cin >> grid[i][j];
    }

    cout << maxBenefit(grid) << "\n";
    return 0;
}

题目内容

某区域被划分为$n×n$的网格区域，用于部署$5G$网络。初始时，所有网格都处于信号未强化覆盖状态。网络工程师可以执行任意次优化操作:选择任意一个网络格，对第$i$列中从顶到底的所有网络格启动信号强化覆盖，该网络格将被标记为“强化覆盖”状态。

在经网络格强化覆盖操作后，对于处于“未强化覆盖”状态的网络格$(i,j)$，如果其左侧或右侧相邻网络格中至少有一个处于“强化覆盖”状态，那么该网络格的信号将得到利用，其$grid[i][j]$的值，将被计入总效益。

请编写代码返回通过任意次优化操作后，该区域能达到的最大总效益。

输入描述

第一行输入一个整数，表示$n$。

后$n$行每行输入$n$个整数，表示$grid$。

输出描述

一个整数，表示通过任意次优化操作后，该区域能达到的最大总效益。

样例1

输入

5
0 0 0 0 0
0 0 3 0 0
0 1 0 0 0
5 0 0 3 0
0 0 0 0 2

输出

11

提示

$1 <= n == grid.length <=100$

$n = grid[i].length$

$0 <= grid[i][j]<= 10^9$