90分#2超时求过

P1434 [SHOI2002] 滑雪

NARCISSUSyl @ 2022-08-11 21:47:07

#include<iostream>
using namespace std;
int hs,ls,c[101][101],num,low[101][101],up[101][101];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int la(int x,int y)
{
    if (low[x][y]==1)return 1;
    else low[x][y] = 1;
    for (int i=0;i<4;i++)
    {
        int xx = x+dx[i];
        int yy = y+dy[i];
        if (xx<=hs&&xx>0&&yy<=ls&&yy>0)
        {
            if (c[xx][yy]<c[x][y])
            {
                low[xx][yy] = la(xx,yy);
                low[x][y] = max(low[x][y],low[xx][yy]+1);
            }
        }
    }
    return low[x][y];
}
int per(int x,int y)
{
    if (up[x][y]==1)return 1;
    else up[x][y] = 1;
    for (int i=0;i<4;i++)
    {
        int xx = x+dx[i];
        int yy = y+dy[i];
        if (xx<=hs&&xx>0&&yy<=ls&&yy>0)
        {
            if (c[xx][yy]>c[x][y])
            {
                up[xx][yy] = per(xx,yy);
                up[x][y] = max(up[x][y],up[xx][yy]+1);
            }
        }
    }
    return up[x][y];
}
int main()
{
    cin>>hs>>ls;
    for(int i = 1;i <= hs;i++)
    {
        for (int j = 1; j <= ls;j++)
        {
            cin>>c[i][j];
        }
    }
    for(int i = 1;i <= hs;i++)
    {
        for (int j = 1; j <= ls;j++)
        {
            num = max(la(i,j)+per(i,j)-1,num);
        }
    }
    cout<<num;
    return 0;
}

by _Virgo_ @ 2022-08-11 22:00:50

@KLEE_LYL 虽然我有点不太明白你的 laper 函数,但盲猜大概是实现了 dfs 的功能,但此题的是要 记忆化搜索 的。


by zhaoqicheng2007 @ 2022-08-15 17:53:53

两个函数留一个就行了


by zhaoqicheng2007 @ 2022-08-15 18:00:24

@KLEE_LYL

"low[xx][yy]=la(xx,yy);"把前半句去了, per函数和up数组删掉,然后比较时取la(i,j)与num的max;


|