求 n×nn×n 的环状方阵上的最大子矩阵和。
构造 2*n *( 2*n) 的正方形
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N=300; int a[N][N],s[N][N],n; int S(int x1,int y1,int x2,int y2){ return s[x2][y2]+s[x1-1][y1-1]- s[x1-1][y2]-s[x2][y1-1]; } void sov(){ int i,j; memset(s,0,sizeof s); cin>>n; for(i=1;i<=n;++i) for(j=1;j<=n;++j) cin>>a[i][j]; for(i=1;i<=2*n;++i) for(j=1;j<=2*n;++j){ a[i][j]=a[(i-1)%n+1][(j-1)%n+1]; } for(i=1;i<=2*n;++i) for(j=1;j<=2*n;++j){ s[i][j]=s[i-1][j]+s[i][j-1]- s[i-1][j-1]+a[i][j]; } int ans=0; for(i=1;i<=2*n;++i) for(j=1;j<=2*n;j++) for(int k=i;k<=min(i+n-1,2*n);k++) for(int l=j;l<=min(j+n-1,2*n);l++){ ans=max(ans,S(i,j,k,l)); } cout<<ans<<endl; } signed main(){ int tes; cin>>tes; while(tes--) sov(); }