[P3625][APIO2009]采油区域 (前缀和)

时间：2024-08-08 08:05:13

这道题用二维前缀和可以做

难度还不算高，细节需要注意

调试了很久……

主要是细节太多了

#include<bits/stdc++.h>

using namespace std;

#define max(a,b) (a>b?a:b)

#define min(a,b) (a<b?a:b)

#define ll long long

#define N 1505

inline int read() {

    int f = , x = ; char ch;

    do { ch = getchar(); if (ch == '-')f = -; } while (ch<'' || ch>'');

    do { x = x *  + ch - ''; ch = getchar(); } while (ch >= ''&&ch <= '');

    return f * x;

}

int m, n, k, ans;

int s[N][N],a[N][N],b[N][N],c[N][N],d[N][N];

int main()

{

    n = read(), m = read(), k = read();

    for (int i = ; i <= n; i++)

    {

        for (int j = ; j <= m; j++)

        {

            int t = read();

            s[i][j] = s[i - ][j] + s[i][j - ] - s[i - ][j - ] + t;

        }

    }

    for (int i = n; i >= k; i--)

        for (int j = m; j >= k; j--)

            s[i][j] -= s[i - k][j] + s[i][j - k] - s[i - k][j - k];

    for (int i = k; i <= n; i++)

        for (int j = k; j <= m; j++)

            a[i][j] = max(s[i][j], max(a[i - ][j], a[i][j - ]));

    for (int i = k; i <= n; i++)

        for (int j = m; j >= k; j--)

            b[i][j] = max(s[i][j], max(b[i][j + ], b[i - ][j]));

    for (int i = n; i >= k; i--)

        for (int j = k; j <= m; j++)

            c[i][j] = max(s[i][j], max(c[i][j - ], c[i + ][j]));

    for (int i = n; i >= k; i--)

        for (int j = m; j >= k; j--)

            d[i][j] = max(s[i][j], max(d[i][j + ], d[i + ][j]));

    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 + k] + c[i + k][m]);

    for (int i = k + k; i <= n; i++)//

        for (int j = k; j <= m - k; j++)

            ans = max(ans, c[i][j] + d[i][j + k] + a[i - k][m]);

    for (int i = k + k; i <= n - k; i++)//

        for (int j = k; j <= m; j++)

            ans = max(ans, s[i][j] + a[i - k][m] + c[i + k][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 + k][j] + b[n][j + k]);

    for (int i = k; i <= n - k; i++)//

        for (int j = k + k; j <= m; j++)

            ans = max(ans, a[n][j - k] + b[i][j] + d[i + k][j]);

    for (int i = k; i <= n - k; i++)//

        for (int j = k + k; j <= m - k; j++)

            ans = max(ans, s[i][j] + a[n][j - k] + b[n][j + k]);

    cout << ans;

    return ;

}

相关文章