递推

CodeForces 173C Spiral Maximum

Posted on

真是天真了,在计算器上计算复杂度在 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;
}