为什么会MLE三个点。。。。。

P1736 创意吃鱼法

wjzcom @ 2016-11-16 15:17:47

//luogu 1736 wjz3 dp 1611161450
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 2500 + 10;
int n, m;
int map[MAXN][MAXN], dd[MAXN][MAXN], f[MAXN][MAXN];   //dd:计算0时需要用到 
struct dis
{
    int x, y;
} d[MAXN][MAXN];     //用于计算所有的0横轴和纵轴的最大连续距离
int main()
{
    cin >> n >> m;
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= m; j++)
            dd[i][j] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            cin >> map[i][j];
            dd[i][j] = map[i][j];
        }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(map[i][j]) f[i][j] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            d[i][j].x = d[i][j].y = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) if(dd[i][j] == 0)
        {
            if(dd[i][j-1] == 0) d[i][j].x = d[i][j-1].x + 1;
            if(dd[i-1][j] == 0) d[i][j].y = d[i-1][j].y + 1;
        }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(map[i][j])
                if(!map[i][j-1] && !map[i-1][j] && map[i-1][j-1])
                {
                   int u = f[i-1][j-1];
                   int v = min(f[i-1][j-1], min(d[i-1][j].y, d[i][j-1].x));
                   f[i][j] = v + 1;
                }
    int maxx = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            maxx = max(maxx, f[i][j]);
            if(map[i][j]) f[i][j] = 1;
            else f[i][j] = 0;   
        }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            d[i][j].x = d[i][j].y = 1;

    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 1; j--) if(dd[i][j] == 0)
        {
            if(dd[i][j+1] == 0) d[i][j].x = d[i][j+1].x + 1;
            if(dd[i-1][j] == 0) d[i][j].y = d[i-1][j].y + 1;
        }

    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 1; j--)
            if(map[i][j])
                if(!map[i][j+1] && !map[i-1][j] && map[i-1][j+1])
                {
                   int u = f[i-1][j+1];
                   int v = min(f[i-1][j+1], min(d[i-1][j].y, d[i][j+1].x));
                   f[i][j] = v + 1;
                }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            maxx = max(f[i][j], maxx);
    cout << maxx;
    system("pause");
    return 0;
}

by psk2016 @ 2017-07-13 16:02:11

@wjzcom 你开的数组太大了(最大128.9MB)!建议调小一点MAXN,或者换一个更优的算法。


by c201904 @ 2017-07-30 10:56:30

把maxn调为2501


|