宝贝，生日快乐！！！LevOJ P1837 切出最好吃的蛋糕

思路:

显然，暴力法需要 O(n^4) 的选点， O(n^2) 的求和，总复杂度 O(n^6) ，超时了。

考虑用如下方法优化。

用 a[x] [y] 表示从点 (1,1) 到点 (x,y) 的所有点之和，则从点 (x1,x2) 到点 (x2,y2) 的和可以表示为：

$a[x2][y2]+a[x1-1][y1-1]-a[x1-1][y2]-a[x2][y1-1]$

枚举所有点更新最大值输出即可。

AC代码：

#include<bits/stdc++.h>
#define int long long

using namespace std;

int x,n;
int a[105][105];
int ans=-1e9;

int sum(int x1,int y1,int x2,int y2){
    return a[x2][y2]+a[x1-1][y1-1]-a[x1-1][y2]-a[x2][y1-1];
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>x;
            a[i][j]=a[i][j-1]+a[i-1][j]-a[i-1][j-1]+x;
        }
    }
    for(int x1=1;x1<=n;x1++){
        for(int y1=1;y1<=n;y1++){
            for(int x2=x1;x2<=n;x2++){
                for(int y2=y1;y2<=n;y2++){
                    ans=max(ans,sum(x1,y1,x2,y2));
                }
            }
        }
    }
    cout<<ans;
    return 0;
}