第3题-分土地 - Problem Detail - CodeFun2000

ID: 462

Type: Default

1000ms

256MiB

Difficulty: 6

Uploaded By:

Tags>

美团

思路：前缀和

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

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

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

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