题解 | 分田地_牛客博客

解题思路

这是一个矩阵分割问题。要求将矩阵横竖各切三刀分成16份，使得最小的一份的价值尽可能大。可以使用二分查找来确定最优值，并用二维前缀和优化区域和的计算。

算法步骤：

预处理二维前缀和数组
二分查找可能的最小值
对每个最小值，检查是否存在合法的切割方案：
- 枚举三个横切位置
- 从左到右贪心地寻找四个竖切位置
- 如果找到合法方案则返回true
返回最大的可行最小值

代码

cpp
java
python

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 76;
int matrix[MAXN][MAXN];
int preSum[MAXN][MAXN];
char line[MAXN];

// 计算区域和
int getRegionSum(int row1, int col1, int row2, int col2) {
    return preSum[row2][col2] - preSum[row2][col1] 
           - preSum[row1][col2] + preSum[row1][col1];
}

// 检查给定最小值是否可行
bool checkMinValue(int rows, int cols, int target) {
    for (int cut1 = 1; cut1 < rows - 2; ++cut1) {
        for (int cut2 = cut1 + 1; cut2 < rows - 1; ++cut2) {
            for (int cut3 = cut2 + 1; cut3 < rows; ++cut3) {
                int prevCut = 0, validCuts = 0;
                
                // 贪心寻找竖切位置
                for (int currCol = 1; currCol <= cols; ++currCol) {
                    int area1 = getRegionSum(0, prevCut, cut1, currCol);
                    int area2 = getRegionSum(cut1, prevCut, cut2, currCol);
                    int area3 = getRegionSum(cut2, prevCut, cut3, currCol);
                    int area4 = getRegionSum(cut3, prevCut, rows, currCol);
                    
                    if (min({area1, area2, area3, area4}) >= target) {
                        prevCut = currCol;
                        validCuts++;
                    }
                    if (validCuts >= 4) return true;
                }
            }
        }
    }
    return false;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    
    // 读取矩阵
    for (int i = 0; i < n; ++i) {
        scanf("%s", line);
        for (int j = 0; j < m; ++j) {
            matrix[i][j] = line[j] - '0';
        }
    }
    
    // 计算前缀和
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] 
                          + matrix[i-1][j-1];
        }
    }
    
    // 二分查找最优解
    int left = 0, right = preSum[n][m];
    int result = 0;
    
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (checkMinValue(n, m, mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    printf("%d\n", result);
    return 0;
}

import java.util.*;

public class Main {
    private int getRegionSum(int[][] preSum, int row1, int col1, int row2, int col2) {
        return preSum[row2][col2] - preSum[row2][col1] 
               - preSum[row1][col2] + preSum[row1][col1];
    }
    
    private boolean checkMinValue(int[][] preSum, int rows, int cols, int target) {
        for (int cut1 = 1; cut1 < rows - 2; cut1++) {
            for (int cut2 = cut1 + 1; cut2 < rows - 1; cut2++) {
                for (int cut3 = cut2 + 1; cut3 < rows; cut3++) {
                    int prevCut = 0;
                    int validCuts = 0;
                    
                    // 贪心寻找竖切位置
                    for (int currCol = 1; currCol <= cols; currCol++) {
                        int area1 = getRegionSum(preSum, 0, prevCut, cut1, currCol);
                        int area2 = getRegionSum(preSum, cut1, prevCut, cut2, currCol);
                        int area3 = getRegionSum(preSum, cut2, prevCut, cut3, currCol);
                        int area4 = getRegionSum(preSum, cut3, prevCut, rows, currCol);
                        
                        if (Math.min(Math.min(area1, area2), Math.min(area3, area4)) >= target) {
                            prevCut = currCol;
                            validCuts++;
                        }
                        
                        if (validCuts >= 4) {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }
    
    public int solve(char[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        
        // 计算前缀和
        int[][] preSum = new int[rows + 1][cols + 1];
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] 
                              + (matrix[i-1][j-1] - '0');
            }
        }
        
        // 二分查找最优解
        int left = 0, right = preSum[rows][cols];
        int result = 0;
        
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (checkMinValue(preSum, rows, cols, mid)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();
        
        char[][] matrix = new char[n][m];
        for (int i = 0; i < n; i++) {
            matrix[i] = sc.nextLine().toCharArray();
        }
        
        Main solution = new Main();
        System.out.println(solution.solve(matrix));
        
        sc.close();
    }
}

class Solution:
    def get_region_sum(self, pre_sum, row1, col1, row2, col2):
        return pre_sum[row2][col2] - pre_sum[row2][col1] \
               - pre_sum[row1][col2] + pre_sum[row1][col1]
    
    def check_min_value(self, pre_sum, rows, cols, target):
        for cut1 in range(1, rows - 2):
            for cut2 in range(cut1 + 1, rows - 1):
                for cut3 in range(cut2 + 1, rows):
                    prev_cut = 0
                    valid_cuts = 0
                    
                    # 贪心寻找竖切位置
                    for curr_col in range(1, cols + 1):
                        area1 = self.get_region_sum(pre_sum, 0, prev_cut, cut1, curr_col)
                        area2 = self.get_region_sum(pre_sum, cut1, prev_cut, cut2, curr_col)
                        area3 = self.get_region_sum(pre_sum, cut2, prev_cut, cut3, curr_col)
                        area4 = self.get_region_sum(pre_sum, cut3, prev_cut, rows, curr_col)
                        
                        if min(area1, area2, area3, area4) >= target:
                            prev_cut = curr_col
                            valid_cuts += 1
                        
                        if valid_cuts >= 4:
                            return True
        return False
    
    def solve(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        
        # 计算前缀和
        pre_sum = [[0] * (cols + 1) for _ in range(rows + 1)]
        for i in range(1, rows + 1):
            for j in range(1, cols + 1):
                pre_sum[i][j] = pre_sum[i-1][j] + pre_sum[i][j-1] - pre_sum[i-1][j-1] \
                               + int(matrix[i-1][j-1])
        
        # 二分查找最优解
        left, right = 0, pre_sum[rows][cols]
        result = 0
        
        while left <= right:
            mid = (left + right) // 2
            if self.check_min_value(pre_sum, rows, cols, mid):
                result = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return result

# 读取输入
n, m = map(int, input().split())
matrix = [input() for _ in range(n)]

solution = Solution()
print(solution.solve(matrix))

算法及复杂度

算法

二分查找
贪心
前缀和

时间复杂度

预处理前缀和： $O(nm)$
二分查找： $O(\log{sum})$ ，其中sum是矩阵元素总和
检查每个最小值： $O(n^3m)$
总时间复杂度： $O(n^3m\log{sum})$

空间复杂度

前缀和数组： $O(nm)$
总空间复杂度： $O(nm)$