为啥用深搜能得90分？（虽然DP已经AC了）（困惑）

hsx_std @ 2021-05-05 21:10:22

#include<bits/stdc++.h>
using namespace std;
int ans=1;
int r,c;
int a[105][105];
void dfs(int pos1,int pos2,int xzs)
{
    if(a[pos1][pos2]<a[pos1-1][pos2] && a[pos1][pos2]<a[pos1+1][pos2] && a[pos1][pos2]<a[pos1][pos2-1] && a[pos1][pos2]<a[pos1][pos2+1])
    {
        if(xzs+1>ans)   ans=xzs+1;
        return;
    }
    if(a[pos1][pos2]>a[pos1-1][pos2])   dfs(pos1-1,pos2,xzs+1);
    if(a[pos1][pos2]>a[pos1+1][pos2])   dfs(pos1+1,pos2,xzs+1);
    if(a[pos1][pos2]>a[pos1][pos2-1])   dfs(pos1,pos2-1,xzs+1);
    if(a[pos1][pos2]>a[pos1][pos2+1])   dfs(pos1,pos2+1,xzs+1);
}
int main()
{
    cin>>r>>c;
    for(int i=0;i<=r+1;i++)
    {
        a[i][0]=10000000;
        a[i][c+1]=10000000;
    }
    for(int i=0;i<=c+1;i++)
    {
        a[0][i]=10000000;
        a[r+1][i]=10000000;
    }
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            dfs(i,j,0);
        }
    }
    cout<<ans<<endl;
    return 0;
}

by fairfairy @ 2021-05-11 13:48:27

@hushengxi 同样的代码，同样的分数，需要记忆化搜索一下子

（我的错误代码）

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>

using namespace std;

int R , C;
int a[110][110];
int ans = 0 , ans_len = 0;

void bfs( int x , int y , int len )
{
    if(!(x >= 1 && y >= 1 && x <= R && y <= C)) return ;
    ans_len = max( ans_len , len );
    if( a[x+1][y] < a[x][y] )
    bfs(x+1,y,len+1);
    if( a[x][y+1] < a[x][y] )
    bfs(x,y+1,len+1);
    if( a[x-1][y] < a[x][y] )
    bfs(x-1,y,len+1);
    if( a[x][y-1] < a[x][y] )
    bfs(x,y-1,len+1);
}

int main()
{
    scanf("%d%d",&R,&C);
    for(int i = 1;i <= R;i ++)
    {
        for(int j = 1;j <= C;j ++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    for(int i = 1;i <= R;i ++)
    {
        for(int j = 1;j <= C;j ++)
        {
            bfs(i,j,1);
        }
    }
    cout << ans_len << endl;
    return 0;
}

实际上需要再开一个二维数组，并且从小到大搜来找最长路径（来自蒟蒻的无奈）

（验证码ngtf）

by fairfairy @ 2021-05-11 13:49:40

其实还是dp香

by hsx_std @ 2021-05-11 17:46:32

嗯嗯（hhh)