求助大佬,搜索的思路

P1434 [SHOI2002] 滑雪

井——— @ 2018-09-14 10:20:30

#include<iostream>
using namespace std;
int m,n,ans=-1;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};    
int a[110][110];
void dfs(int x,int y,int len)
{
    if(x<1||x>m||y<1||y>n)                          //防止越界 
        return;
    for(int i=0;i<4;i++)
    {
        if(a[x+dx[i]][y+dy[i]]<a[x][y])             //找周围小的点进行操作 
        {
            dfs(x+dx[i],y+dy[i],len+1);
            ans=max(ans,len);                       //更新最大值 
        }
    }
}
int main()
{
    cin>>m>>n;
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
        cin>>a[i][j];
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
    {
    //易知:如果周围有比这个点高的点,
    //  那么这个点就不是最优解
        if(a[i][j]>a[i+1][j]&&i+1<=m)
        if(a[i][j]>a[i][j+1]&&j+1<=n)
        if(a[i][j]>a[i][j-1]&&j-1>0)
            dfs(i,j,1);                         //长度为1,开始寻找 
    }
    cout<<ans;
    return 0;
 } 

最后只得了20分,求大佬告诉我思维的局限性在哪,1个tle,7个wa


by stepsys @ 2018-09-14 12:03:54

TLE是因为这题要记忆化搜索


by 梧桐灯 @ 2018-09-14 12:32:38

更新最大值有点问题。。


by 7KByte @ 2018-09-14 12:57:04

用dp来做


by 7KByte @ 2018-09-14 12:58:30

先按数值从小到大排(用稀疏矩阵),再做dp,不过这题最好用记忆化搜索来做


by 7KByte @ 2018-09-14 12:58:44

@井———


by 井——— @ 2018-09-14 14:26:56

@犇羴鱻赑骉 麻烦大佬点一下哪里,我看了好久了


by 井——— @ 2018-09-14 14:27:47

@online_wlq 谢谢大佬,我知道正解,但我想搞明白我哪里写错了


by 梧桐灯 @ 2018-09-16 21:11:10

@井———

最好每次dfs return前写 因为你的if语句可能每一次都不对,但如果此时恰是最大值时,就无法更新了(语文不好的我已经尽力了QAQ)


|