一个点MLE心累,应该没有比我更耗内存的代码了。。。

P1736 创意吃鱼法

贞白铁战逸 @ 2018-09-11 23:26:53

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int a[2505][2505], v[2505][2505], u[2505][2505], maxx = 0;
int n, m;
struct node
{
    int up, left, right;
}f[2505][2505];
int main()
{
    int i, j, k = 0, l;
    cin >> n >> m;
    for (i = 1; i<= n; i++)
    {
        for (j = 1; j<= m; j++)
        {
            scanf("%d", &a[i][j]);
            if (!a[i][j]) 
            {
                if (i + 1 <= n) f[i + 1][j].up = f[i][j].up + 1;
                if (j + 1 <= m) f[i][j + 1].left = f[i][j].left + 1;
            }
            else 
            {
                l = j;
                v[i][j] = 1;
                u[i][j] = 1;
            }
        f[i][l].right = j - l; 
        }
        for (j =  l - 1; j >= 1; j--)
        {
            if (a[i][j])
            {
                f[i][j].right = f[i][l].left;
                l = j;
            }
        }
    }
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            if (a[i][j])
            {
                if (f[i][j].up >= v[i - 1][j - 1] && f[i][j].left >= v[i - 1][j - 1])
                {
                    v[i][j] = v[i - 1][j - 1] + 1;
                }
                else
                {
                    v[i][j] = min(f[i][j].up, f[i][j].left) + 1;
                }
            }
            k = m - j + 1;
            if (a[i][k])
            {
                if (f[i][k].up >= u[i - 1][k + 1] && f[i][k].right >= u[i - 1][k + 1])
                {
                    u[i][k] = u[i - 1][k + 1] + 1;
                }
                else
                {
                    u[i][k] = min(f[i][k].up, f[i][k].right) + 1;
                }
            }
            maxx = max(maxx, max(v[i][j], u[i][k]));
        }   
    cout << maxx;
    //cout << u[3][4] << " " << u[4][3] << " " << u[5][2] << " - " << f[4][3].up << " - " << f[4][3].right;
}

by りゅうこせい @ 2018-09-18 19:22:02

一样一样。。我也是不知道怎么优化了


by 薄荷凉了夏 @ 2018-09-19 14:49:11

其实如果你的``` up!=0


就可以说明你这个位置上原来不是0

所以最开始的矩阵是没必要新开一个存下来的

SO 5个就OK了

by maruize @ 2019-11-30 22:26:32

int 改成 short 即可


|