题解

题意简易描述

塔子哥需要在一个 $n \times m$ 的农场中选择一个矩形区域进行高级培育技术的引进，以最大化农场的年利润。每个地块有一个预估的收入，选择的区域的利润计算公式为：

最大利润 = 选中区域中各地块收入总和 - 选中地块数 × 5

如果存在多个区域具有相同的最大利润，则选择引进地块数最少的区域。如果所有区域的利润都是负数，则选择损失最少的单个地块。

输入包括农场的大小和每个地块的收入，输出应为选择的地块数和对应的最大利润。

题解思路

1. 利润计算转换：

   • 每个地块的利润为 收入 - 5。这样，选择区域的总利润就是所有地块的 (收入 - 5) 的和。
   • 如果全部地块的 (收入 - 5) 都为负数，意味着选择任何区域都会带来负利润，此时需要选择损失最少的单个地块。

2. 最大子矩形和问题：

   • 将问题转化为在二维数组中找到一个子矩形，其元素和最大。
   • 使用Kadane算法的二维版本来解决此问题。具体步骤如下：
     • 固定两个行边界 top 和 bottom，然后将这两行之间每列的值累加，转化为一维数组。
     • 对这个一维数组应用Kadane算法，找到最大子数组和。
     • 同时记录选择的地块数，以便在利润相同的情况下选择地块数更少的方案。

3. 处理所有负利润的情况：

   • 如果所有地块的 (收入 - 5) 都为负数，选择单个地块中损失最少的那个地块。

4. 记录最大利润和最小地块数：

   • 在遍历过程中，持续更新最大利润和对应的最小地块数。

复杂度分析

• 时间复杂度：$O(n^2 \times m)$

  • 外层双重循环遍历所有可能的上下边界，共 $O(n^2)$ 种。
  • 内层对每一列进行累加并应用Kadane算法，时间复杂度为 $O(m)$。

• 空间复杂度：$O(m)$

  • 使用一个一维数组 temp 存储每列的累加值。

代码

Python 代码

def max_profit(n, m, matrix):
    # 将每个地块的收入减去5，得到modified_matrix
    modified_matrix = [[cell - 5 for cell in row] for row in matrix]
    
    max_profit = float('-inf')  # 初始化最大利润为负无穷
    min_blocks = 0  # 初始化最小地块数

    # 遍历所有可能的上下边界
    for top in range(n):
        temp = [0] * m  # 初始化临时数组
        for bottom in range(top, n):
            # 累加每列的收入
            for col in range(m):
                temp[col] += modified_matrix[bottom][col]
            
            # 应用Kadane算法，寻找最大子数组和，并记录地块数
            current_sum = 0
            current_blocks = 0
            for col in range(m):
                if current_sum + temp[col] > temp[col]:
                    current_sum += temp[col]
                    current_blocks += (bottom - top + 1)
                else:
                    current_sum = temp[col]
                    current_blocks = (bottom - top + 1)
                # 更新最大利润和最小地块数
                if current_sum > max_profit:
                    max_profit = current_sum
                    min_blocks = current_blocks
                elif current_sum == max_profit and current_blocks < min_blocks:
                    min_blocks = current_blocks

    # 如果最大利润小于0，选择最小的损失
    if max_profit < 0:
        min_loss = float('inf')
        min_blocks = 1
        for i in range(n):
            for j in range(m):
                loss = matrix[i][j] - 5
                if loss > max_profit:
                    max_profit = loss
        return min_blocks, max_profit
    else:
        return min_blocks, max_profit

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    m = int(data[1])
    matrix = []
    idx = 2
    for _ in range(n):
        row = list(map(int, data[idx:idx + m]))
        matrix.append(row)
        idx += m
    blocks, profit = max_profit(n, m, matrix)
    print(blocks, profit)

if __name__ == "__main__":
    main()

Java 代码

import java.util.Scanner;

public class Main {
    public static int[] maxProfit(int n, int m, int[][] matrix) {
        // 将每个地块的收入减去5，得到modified_matrix
        int[][] modifiedMatrix = new int[n][m];
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                modifiedMatrix[i][j] = matrix[i][j] - 5;
            }
        }

        int maxProfit = Integer.MIN_VALUE; // 初始化最大利润为负无穷
        int minBlocks = 0; // 初始化最小地块数

        // 遍历所有可能的上下边界
        for(int top=0; top<n; top++) {
            int[] temp = new int[m];
            for(int bottom=top; bottom<n; bottom++) {
                // 累加每列的收入
                for(int col=0; col<m; col++) {
                    temp[col] += modifiedMatrix[bottom][col];
                }

                // 应用Kadane算法，寻找最大子数组和，并记录地块数
                int currentSum = 0;
                int currentBlocks = 0;
                for(int col=0; col<m; col++) {
                    if(currentSum + temp[col] > temp[col]) {
                        currentSum += temp[col];
                        currentBlocks += (bottom - top + 1);
                    } else {
                        currentSum = temp[col];
                        currentBlocks = (bottom - top + 1);
                    }
                    // 更新最大利润和最小地块数
                    if(currentSum > maxProfit) {
                        maxProfit = currentSum;
                        minBlocks = currentBlocks;
                    }
                    else if(currentSum == maxProfit && currentBlocks < minBlocks) {
                        minBlocks = currentBlocks;
                    }
                }
            }
        }

        // 如果最大利润小于0，选择最小的损失
        if(maxProfit < 0) {
            maxProfit = Integer.MIN_VALUE;
            minBlocks = 1;
            for(int i=0;i<n;i++) {
                for(int j=0;j<m;j++) {
                    int loss = matrix[i][j] - 5;
                    if(loss > maxProfit) {
                        maxProfit = loss;
                    }
                }
            }
        }

        return new int[]{minBlocks, maxProfit};
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] matrix = new int[n][m];
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }
        int[] result = maxProfit(n, m, matrix);
        System.out.println(result[0] + " " + result[1]);
    }
}

C++ 代码

#include <bits/stdc++.h>
using namespace std;

pair<int, int> maxProfit(int n, int m, vector<vector<int>> &matrix) {
    // 将每个地块的收入减去5，得到modified_matrix
    vector<vector<int>> modifiedMatrix(n, vector<int>(m, 0));
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            modifiedMatrix[i][j] = matrix[i][j] - 5;
        }
    }

    int maxProfitVal = INT32_MIN; // 初始化最大利润为负无穷
    int minBlocks = 0; // 初始化最小地块数

    // 遍历所有可能的上下边界
    for(int top=0; top<n; top++) {
        vector<int> temp(m, 0);
        for(int bottom=top; bottom<n; bottom++) {
            // 累加每列的收入
            for(int col=0; col<m; col++) {
                temp[col] += modifiedMatrix[bottom][col];
            }

            // 应用Kadane算法，寻找最大子数组和，并记录地块数
            int currentSum = 0;
            int currentBlocks = 0;
            for(int col=0; col<m; col++) {
                if(currentSum + temp[col] > temp[col]) {
                    currentSum += temp[col];
                    currentBlocks += (bottom - top + 1);
                }
                else {
                    currentSum = temp[col];
                    currentBlocks = (bottom - top + 1);
                }
                // 更新最大利润和最小地块数
                if(currentSum > maxProfitVal) {
                    maxProfitVal = currentSum;
                    minBlocks = currentBlocks;
                }
                else if(currentSum == maxProfitVal && currentBlocks < minBlocks) {
                    minBlocks = currentBlocks;
                }
            }
        }
    }

    // 如果最大利润小于0，选择最小的损失
    if(maxProfitVal < 0) {
        maxProfitVal = INT32_MIN;
        minBlocks = 1;
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                int loss = matrix[i][j] - 5;
                if(loss > maxProfitVal) {
                    maxProfitVal = loss;
                }
            }
        }
    }

    return make_pair(minBlocks, maxProfitVal);
}

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> matrix(n, vector<int>(m, 0));
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin >> matrix[i][j];
        }
    }
    pair<int, int> result = maxProfit(n, m, matrix);
    cout << result.first << " " << result.second;
    return 0;
}

JavaScript 代码

function maxProfit(n, m, matrix) {
    // 将每个地块的收入减去5，得到modified_matrix
    let modifiedMatrix = Array.from({length: n}, () => Array(m).fill(0));
    for(let i=0;i<n;i++) {
        for(let j=0;j<m;j++) {
            modifiedMatrix[i][j] = matrix[i][j] - 5;
        }
    }

    let maxProfitVal = -Infinity; // 初始化最大利润为负无穷
    let minBlocks = 0; // 初始化最小地块数

    // 遍历所有可能的上下边界
    for(let top=0; top<n; top++) {
        let temp = Array(m).fill(0);
        for(let bottom=top; bottom<n; bottom++) {
            // 累加每列的收入
            for(let col=0; col<m; col++) {
                temp[col] += modifiedMatrix[bottom][col];
            }

            // 应用Kadane算法，寻找最大子数组和，并记录地块数
            let currentSum = 0;
            let currentBlocks = 0;
            for(let col=0; col<m; col++) {
                if(currentSum + temp[col] > temp[col]) {
                    currentSum += temp[col];
                    currentBlocks += (bottom - top + 1);
                }
                else {
                    currentSum = temp[col];
                    currentBlocks = (bottom - top + 1);
                }
                // 更新最大利润和最小地块数
                if(currentSum > maxProfitVal) {
                    maxProfitVal = currentSum;
                    minBlocks = currentBlocks;
                }
                else if(currentSum === maxProfitVal && currentBlocks < minBlocks) {
                    minBlocks = currentBlocks;
                }
            }
        }
    }

    // 如果最大利润小于0，选择最小的损失
    if(maxProfitVal < 0) {
        maxProfitVal = -Infinity;
        minBlocks = 1;
        for(let i=0;i<n;i++) {
            for(let j=0;j<m;j++) {
                let loss = matrix[i][j] - 5;
                if(loss > maxProfitVal) {
                    maxProfitVal = loss;
                }
            }
        }
    }

    return [minBlocks, maxProfitVal];
}

// 读取输入并输出结果
function main() {
    const fs = require('fs');
    const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split(/\s+/);
    let idx = 0;
    const n = parseInt(input[idx++]);
    const m = parseInt(input[idx++]);
    let matrix = [];
    for(let i=0;i<n;i++) {
        let row = [];
        for(let j=0;j<m;j++) {
            row.push(parseInt(input[idx++]));
        }
        matrix.push(row);
    }
    const [blocks, profit] = maxProfit(n, m, matrix);
    console.log(blocks + " " + profit);
}

main();

题目内容

小明正在承包月亮市星星区的一片农场。为了提高农场的利润，小明打算选取部分区域引进高级培育技术。已知进行试点的区域的农作物价值计算公式如下：最大利润 = 选中区域中的各地块收入总和 - 区域内地块个数 $\times$ $5$。 整个农场区域是一个矩形区域，被划分为 $n \times m$ 个地块。在进行规划前，农场技术人员对每个地块进行了勘测，计算出每个地块的最大年产量，使用 $n \times m$ 矩阵表示。

为了最大化农场的利润，并降低管理成本，小明打算选择一个矩形区域引进高级培育技术。他想知道，应该选择多少个地块进行引进高级培育技术，以获得最大的年利润。

请实现一个功能，求出应该引进高级培育技术的地块数量，以及能够获得的最大年利润。

输入描述

输入第一行为两个正整数: $n$ 、$m$, 使用空格分隔。其中$A$ 地区分成为 $n$ $\times$ $m$ 个地块： $1$ $\leq$ $m,n$ $\leq$ $100$,

接下来 $n$行 ,每行 $m$ 个正整数。表示每小块区域面积的最大利润收入。$0$ $\leq$ 收入 $\leq$ $100$.

输出描述

输出一行为两个整数值，使用空格分隔。第一个值表示引进高级培育技术的地块数，第二个值表示最大利润。

注意：如果存在最大利润相同的情况，则输出引进高级培育技术较小的结果

如果所有地块利润都是负数，则需选择损失最少的那个地块，引进高级培育技术。

样例1

输入

3 3
2 6 9
9 4 9
8 7 3

输出

9 12

解释

全部选择

样例2

输入

3 3
2 6 1
1 4 1
8 7 3

输出

2 5

解释

可以证明，选择左下角那个8和7是最优解。面积是8+7 =15 , 大小是 15 - 5*2 = 5