真是天真了，在计算器上计算复杂度在 1e8 ,给了 3s 时间以为侥幸能过，就用暴力写了……
结果拖到最后也没有写出来……
题意：
计算最大的有空行的弓形矩阵值。
思路：
如果说你观察仔细的话，你会发现 5×5 方阵 与 3×3 的方阵 差一个格子互补， 7×7 的 方阵 与 5×5 的方阵 差一个格子互补， 9×9 的 方阵 与7× 7 的方阵 差一个格子互补……
那么我们先预处理好每一个 3×3 方阵的值，再通过递推就能知道每一个方阵的值了
AC Code
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))
using namespace std;
const int maxn = 550;
const int inf = 0x3f3f3f3f;
int n, m, ans;
int mat[maxn][maxn];
int dp[maxn][maxn][2];
int sum[maxn][maxn];
inline int recSum(int x1, int y1, int x2, int y2)
{
return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
}
inline void prepSum()
{
ans = -inf;
range(i, 1, n)
range(j, 1, m)
sum[i][j] = mat[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
inline int solve(int x, int y, int len)
{
if (len == 0)
return dp[x][y][0] = mat[x][y];
else {
dp[x][y][0] = recSum(x, y, x + len, y + len);
dp[x][y][0] -= mat[x + 1][y];
dp[x][y][0] -= dp[x + 1][y + 1][1];
return dp[x][y][0];
}
}
int main()
{
scanf("%d %d", &n, &m);
range(i, 1, n)
range(j, 1, m)
scanf("%d", &mat[i][j]);
prepSum();
range(k, 0, min(n, m))
{
rrange(i, 1, n)
rrange(j, 1, m)
dp[i][j][1] = dp[i][j][0];
rrange(i, 1, n)
{
if (i + k > n)
continue;
rrange(j, 1, m)
{
if (j + k > m)
continue;
int p = solve(i, j, k);
if (k > 0)
ans = max(ans, p);
}
}
k++;
}
printf("%d\n", ans);
return 0;
}