题解 | 小红的蛋糕切割

这是一个枚举问题，可以通过以下步骤解决：

1. 预处理：计算整个蛋糕的总美味度 total使用二维前缀和数组加速区域和的计算
2. 枚举策略：枚举正方形的边长 len（从1到min(n,m)）枚举正方形左上角的位置 (i,j)计算正方形区域的美味度和剩余区域的美味度更新最小差值
3. 具体步骤：构建二维前缀和数组对每个可能的正方形大小和位置：计算正方形区域的美味度和计算剩余区域的美味度和计算两者差值的绝对值维护最小差值

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        // 构建二维前缀和数组
        long[][] sum = new long[n + 1][m + 1];
        long total = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                int x = sc.nextInt();
                total += x;
                sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + x;
            }
        }
        
        long ans = total;
        // 枚举正方形边长
        for(int len = 1; len <= Math.min(n, m); len++) {
            // 枚举左上角位置
            for(int i = 1; i + len - 1 <= n; i++) {
                for(int j = 1; j + len - 1 <= m; j++) {
                    int x1 = i, y1 = j;
                    int x2 = i + len - 1, y2 = j + len - 1;
                    long square = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
                    long remain = total - square;
                    ans = Math.min(ans, Math.abs(square - remain));
                }
            }
        }
        
        System.out.println(ans);
    }
}