思路：前缀和

给定一个矩形，将其分割成两个矩形，要求两个矩形价值和的差尽可能小，输出最小值。

我们可以通过枚举横切及竖切切的长度对矩形进行分割，并使用二维前缀和来$O(1)$的快速获得两个矩阵的价值。

二维矩阵的知识点可以参照P1311华为太阳能发电板的题解讲解。

时间复杂度$O(N^2)$

代码

C++

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

const int maxn=1e3+10;
int n,m;
int x,y;
long long pre[maxn][maxn];
long long a[maxn][maxn];

long long Abs(long long a,long long b){
	return a>b ? a-b:b-a;
}

int main(){
	std::ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>a[i][j];
			pre[i][j]=a[i][j]+pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];
		}
	}
	long long ans=1e9;
	for(int i=1;i<n;++i){
		ans=min(ans,Abs(pre[i][m],pre[n][m]-pre[i][m]));
	}
	for(int j=1;j<m;++j){
		ans=min(ans,Abs(pre[n][j],pre[n][m]-pre[n][j]));
	}
	cout<<ans;
	
	return 0;
}

python

def Abs(a, b):
    return a - b if a > b else b - a

n, m = map(int, input().split())
a = [[0] * (m + 1) for _ in range(n + 1)]
pre = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    row = list(map(int, input().split()))
    for j in range(1, m + 1):
        a[i][j] = row[j - 1]
        pre[i][j] = a[i][j] + pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1]

ans = 1e9
for i in range(1, n):
    ans = min(ans, Abs(pre[i][m], pre[n][m] - pre[i][m]))

for j in range(1, m):
    ans = min(ans, Abs(pre[n][j], pre[n][m] - pre[n][j]))

print(int(ans))

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int maxn = 1010; // maxn is not used in the code
        int n, m;
        long[][] pre = new long[maxn][maxn];
        
        n = scanner.nextInt();
        m = scanner.nextInt();
        
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                pre[i][j] = scanner.nextLong();
                pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
            }
        }
        
        long ans = 1000000000L; // 1e9
        for (int i = 1; i < n; ++i) {
            ans = Math.min(ans, Abs(pre[i][m], pre[n][m] - pre[i][m]));
        }
        
        for (int j = 1; j < m; ++j) {
            ans = Math.min(ans, Abs(pre[n][j], pre[n][m] - pre[n][j]));
        }
        
        System.out.println(ans);
    }
    
    public static long Abs(long a, long b) {
        return a > b ? a - b : b - a;
    }
}

题目描述

小美是一个勤勤恳恳了一辈子的农民，这天，他要将自己种了一辈子的土地分给两个儿子了。

土地的大小为$n*m$，每块土地都有其自己的价值。小美希望能够将土地一分为二为两块完整的矩形土地并分给两个儿子，但是又不想对儿子偏心，因此希望两块土地的价值尽可能接近。

输入描述

第一行输入两个正整数$n$和$m$。

接下来的$n$行，每行$m$个正整数$a_{i,j}$，代表每块土地的价值。

$1 \leq n,m \leq 10^3$

$1 \leq a_i \leq 10^4$

输出描述

输出两块土地价值的差值的绝对值。

样例

输入

5 5
1 1 1 1 1 
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

输出

5