这个题我是不会用dp做,众所周知,能用记忆化搜索的题肯定能用dp,能用dp的不一定用记忆化搜索.
这个题正好用记忆化搜索可以过,欸嘿
#include<bits/stdc++.h> using namespace std; const int N=2020; int f[N][N],a[N][N],n,m,res;//a数组存储状态,f数组存储每条路最大的值 int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}; int dfs(int x,int y) { if(f[x][y]) return f[x][y];//如果本来就存在,那就直接返回 for(int i=0;i<4;i++) { int x1=x+dx[i],y1=y+dy[i]; if(x1<=0||y1<=0||x1>n||y1>m) continue;//切记判断(呜呜) if(a[x][y]>a[x1][y1]) f[x][y]=max(f[x][y],dfs(x1,y1)+1);//看看走x1,y1这条路和现在的路哪个长; } return f[x][y];//返回 } int main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) res=max(res,dfs(i,j));//每条都要搜一下,因为是记忆化搜索,所以有地方已经搜过了,不用担心复杂度 } cout<<res+1; return 0; }
标签:滑雪,int,dfs,y1,x1,OJ3651,dp From: https://www.cnblogs.com/o-Sakurajimamai-o/p/17427972.html