题解 | 小红的蛋糕切割

由于n，m<=1e3，所以直接枚举小红的所有吃法，从1到min(n,m)枚举小红蛋糕的边长，再枚举每个边长下小红蛋糕的左上角坐标，计算小红蛋糕和小紫蛋糕的美味度，并记录差值最小的答案。

计算小红蛋糕和小紫蛋糕的美味度时可以使用二维前缀和预处理原数组，来减少时间复杂度。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double d;
typedef long double ld;
const int N=1e5+10;
const int mod=1e9+7;
ll a[1005][1005]={};
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            a[i][j]+=a[i-1][j]-a[i-1][j-1]+a[i][j-1];//二维前缀和
        }
    }
    ll sum=a[n][m];//总和，用于计算小紫所吃蛋糕美味度
    ll ans=1e10+10;
    for(int p=1;p<min(n,m);p++){//枚举边长
        for(int i=1;i+p<=n;i++){
            for(int j=1;j+p<=m;j++){
                ll aa=a[i+p][j+p]+a[i-1][j-1]-a[i-1][j+p]-a[i+p][j-1];//小红所吃蛋糕美味度
                ll bb=sum-aa;//小紫所吃蛋糕美味度
                ans=min(ans,abs(aa-bb));//记录差值
            }
        }
    }
    cout<<ans<<endl;
	return 0;
}

#牛客春招刷题训练营#+牛客春招刷题训练营