80分求助

P1434 [SHOI2002] 滑雪

路人甲2003 @ 2019-05-19 16:54:34

#include<bits/stdc++.h>
using namespace std;
int a[105][105];
bool b[105][105];
int dp[105][105];
int m,n,sumn,minn=100000000,sx,sy;
int x[4]={0,0,-1,1},y[4]={-1,1,0,0};
int dfs(int xx,int yy)
{
    if(dp[xx][yy]) return dp[xx][yy];
    int path=-1;
    for(register int i=0;i<=3;++i)
    {
        if(!b[xx+x[i]][yy+y[i]]&&xx+x[i]>0&&xx+x[i]<=n
        &&yy+y[i]>0&&yy+y[i]<=m&&a[xx][yy]>a[xx+x[i]][yy+y[i]])
        {
            path=max(path,dfs(xx+x[i],yy+y[i])+1);
        }
    }
    return dp[xx][yy]=path;
}
int main()
{
    cin>>n>>m;
    for(register int i=1;i<=n;++i)
    for(register int j=1;j<=m;++j) 
    {
        scanf("%d",&a[i][j]);
        if(a[i][j]<minn){sx=i;sy=j;minn=a[i][j];}
    }
    dp[sx][sy]=1;
    for(register int i=1;i<=n;++i)
    for(register int j=1;j<=m;++j) 
    {
        dfs(i,j);

    }
    for(register int i=1;i<=n;++i)
    for(register int j=1;j<=m;++j) sumn=max(sumn,dp[i][j]);
    /*
    for(register int i=1;i<=n;++i)
    {
        for(register int j=1;j<=m;++j) 
        {
            printf("%d ",dp[i][j]);
        }
        cout<<endl;
    }
    cout<<endl;*/
    printf("%d",sumn);
    return 0;
}

wa1,10


by hater @ 2019-05-19 17:28:27

dp了解一下


by 路人甲2003 @ 2019-05-24 15:33:40

@hater 这个是记搜,也是dp啊


|