P1719 最大加权矩阵

点击查看代码

#include<bits/stdc++.h>using namespace std;const int N=125;int a[N][N],s[N][N];
int n;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>a[i][j];s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];}}int mx=INT_MIN;for(int x1=1;x1<=n;x1++){for(int y1=1;y1<=n;y1++){for(int x2=1;x2<=n;x2++ ){for(int y2=1;y2<=n;y2++){if(x1>x2||y1>y2) continue;else{int ans=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];mx=max(mx,ans);}}}}}cout<<mx<<endl;return 0;
}

本质上还是二维前缀和的简单应用。考察了四层循环的设置，四层循环四个数字分别对应四个坐标，时间复杂度是o（n……4），但因为给出的n不大所以不会超限，如果用贪心的话就可以把复杂度降到o（n……3）