前言
说实话，这个记忆化搜索呢，硬要说的话，你可以说它是“图型DP优化”（我编的hh）
就是在图论之中搜索然后去除不必要的递归嘛，就是DFS/BFS套个壳。
但毕竟更像是DP，所以就放这吧（树型DP都在呢不是吗）
例题
AcWing901-滑雪
f[i][j]表示从(i,j)开始滑的最长路径。
从上下左右四个方向找就行了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<bits/stdc++.h>
using namespace std;
const int N=305;
int ans;
int r,c;
int a[N][N];
int f[N][N];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int dp(int x,int y){
if(f[x][y]!=0)return f[x][y];
f[x][y]=1;
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(1<=nx&&nx<=r&&1<=ny&&ny<=c&&a[nx][ny]<a[x][y]){
f[x][y]=max(f[x][y],dp(nx,ny)+1);
}
}
return f[x][y];
}
int main(){
cin>>r>>c;
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++){
ans=max(ans,dp(i,j));
}
}
cout<<ans;
return 0;
}
|
完结撒花o(￣︶￣)o