传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1177
【题解】
发现分割方案就只有6种……
稍微分点类，然后大力算出以(i,j)为左上角/左下角/右上角/右下角的二维前缀/后缀内的max正方形即可。
然后大力分六种情况讨论一波，注意边界。
# include <stdio.h> # include <string.h> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 1500 + 10; const int mod = 1e9+7; # define RG register # define ST static int n, m, k, s[M][M]; int p[M][M]; int a[M][M], b[M][M], c[M][M], d[M][M], ans; int main() { scanf("%d%d%d", &n, &m, &k); for (int i=1; i<=n; ++i) for (int j=1, x; j<=m; ++j) { scanf("%d", &x); s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + x; } for (int i=k; i<=n; ++i) for (int j=k; j<=m; ++j) p[i][j] = s[i][j] - s[i-k][j] - s[i][j-k] + s[i-k][j-k]; // 以(i,j)为右下角 for (int i=k; i<=n; ++i) for (int j=k; j<=m; ++j) a[i][j] = max(p[i][j], max(a[i-1][j], a[i][j-1])); // 以(i,j)为左下角 for (int i=k; i<=n; ++i) for (int j=m-k+1; j; --j) { int C = j+k-1; b[i][j] = max(p[i][C], max(b[i-1][j], b[i][j+1])); } // 以(i,j)为右上角 for (int i=n-k+1; i; --i) for (int j=k; j<=m; ++j) { int C = i+k-1; c[i][j] = max(p[C][j], max(c[i+1][j], c[i][j-1])); } // 以(i,j)为左上角 for (int i=n-k+1; i; --i) for (int j=m-k+1; j; --j) { int C1 = i+k-1, C2 = j+k-1; d[i][j] = max(p[C1][C2], max(d[i+1][j], d[i][j+1])); } // 两个竖线 for (int i=k; i<=n; ++i) for (int j=k+k; j<=m-k; ++j) ans = max(ans, p[i][j] + a[n][j-k] + b[n][j+1]); // 两个横线 for (int i=k+k; i<=n-k; ++i) for (int j=k; j<=n; ++j) ans = max(ans, p[i][j] + a[i-k][m] + c[i+1][m]); // 竖线，横线左 for (int i=k; i<=n-k; ++i) for (int j=k; j<=m-k; ++j) ans = max(ans, a[i][j] + c[i+1][j] + d[1][j+1]); // 竖线，横线右 for (int i=k; i<=n-k; ++i) for (int j=k; j<=m-k; ++j) ans = max(ans, a[n][j] + b[i][j+1] + d[i+1][j+1]); // 横线，竖线上 for (int i=k; i<=n-k; ++i) for (int j=k; j<=m-k; ++j) ans = max(ans, a[i][j] + b[i][j+1] + d[i+1][1]); // 横线，竖线下 for (int i=k; i<=n-k; ++i) for (int j=k; j<=m-k; ++j) ans = max(ans, a[i][m] + c[i+1][j] + d[i+1][j+1]); printf("%d ", ans); return 0; }