暴搜
1 #include2 #include 3 #include 4 using namespace std; 5 6 int num[505][505]; 7 int Ans=1,n,m; 8 int fx[4]={ 0,0,1,-1}; 9 int fy[4]={ 1,-1,0,0};10 11 void dfs(int x,int y,int len){12 Ans=max(Ans,len);13 for (int i=0;i<4;i++)14 if (num[x][y]>num[x+fx[i]][y+fy[i]]&&num[x+fx[i]][y+fy[i]]!=-1)15 dfs(x+fx[i],y+fy[i],len+1);16 }17 18 int main(){19 freopen("ski.in","r",stdin);20 freopen("ski.out","w",stdout);21 scanf("%d%d",&n,&m);22 memset(num,-1,sizeof(num));23 for (int i=1;i<=n;i++)24 for (int j=1;j<=m;j++)25 scanf("%d",&num[i][j]);26 for (int i=1;i<=n;i++)27 for (int j=1;j<=m;j++){28 bool is_ok=0;29 for(int t=0;t<=3;t++)30 if (num[i][j]>num[i+fx[t]][j+fy[t]]&&num[i+fx[t]][j+fy[t]]!=-1) is_ok=1;31 if (is_ok==1) dfs(i,j,1); 32 }33 printf("%d",Ans);34 return 0;35 }
直接搜索无法很好的处理重叠子问题，因此可采用记忆化搜索以减少时间
记忆化搜索
1 #include2 #include 3 #include 4 using namespace std; 5 6 int f[505][505];//存储从(i,j)出发可滑的最长路径，避免重复搜索 7 int num[505][505]; 8 int fx[4]={ 0,0,1,-1}; 9 int fy[4]={ 1,-1,0,0};10 11 int dfs(int x,int y){12 int tmp=0;13 if (f[x][y]!=-1) return f[x][y];14 for (int i=0;i<4;i++){15 if (num[x][y]>num[x+fx[i]][y+fy[i]]&&num[x+fx[i]][y+fy[i]]!=-1)16 tmp=max(tmp,dfs(x+fx[i],y+fy[i])+1);17 }18 if (tmp==0) {19 f[x][y]=1;20 return 1;21 }22 f[x][y]=tmp;23 return tmp;24 }25 int main(){26 int ans=1;27 freopen("ski2.in","r",stdin);28 freopen("ski2.out","w",stdout);29 int n,m;30 scanf("%d%d",&n,&m);31 memset(num,-1,sizeof(num));32 memset(f,-1,sizeof(f));33 for (int i=1;i<=n;i++)34 for (int j=1;j<=m;j++)35 scanf("%d",&num[i][j]);36 for (int i=1;i<=n;i++)37 for (int j=1;j<=m;j++)38 ans=max(ans,dfs(i,j));39 printf("%d\n",ans);40 return 0;41 }