题解 | 小美的蛋糕切割

看到很多人说二位前缀和，不禁有些奇怪，有那么复杂吗？这题完全就用不到动态规划呀，纯数字计算不就好了？

说说我的思路，首先维护两个一维数组row和col，分别保存矩阵每一行的元素和，与每一列的元素和。这一步在数据输入的时候就完成了，同时我们还得到了矩阵所有元素的和sum。

接下来分别计算横着切和竖着切，以横着切为例，初始时ans = sum，s1 = 0，s2 = sum。

遍历数组row，s1 += row[i]，s2 -= row[i]。如果s1和s2差的绝对值 < ans，更新ans。当s2 < s1时跳出循环。

竖着切一样操作，只不过吧数组row换成col即可。最后输出ans。

下面贴出c++代码。

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

int main() {
    int n, m, a;
    cin >> n >> m;
    vector<int> row(n, 0), col(m, 0);
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a;
            row[i] += a;
            col[j] += a;
            sum += a;
        }
    }
    long long ans = sum;
    long long s12, s1 = 0, s2 = sum;
    for (int i = 0; i < n; ++i) {
        s1 += row[i];
        s2 -= row[i];
        s12 = abs(s2 - s1);
        ans = min(ans, s12);
        if (s2 < s1) break;
    }
    s1 = 0;
    s2 = sum;
    for (int i = 0; i < m; ++i) {
        s1 += col[i];
        s2 -= col[i];
        s12 = abs(s2 - s1);
        ans = min(ans, s12);
        if (s2 < s1) break;
    }
    cout << ans;
}