https://www.luogu.com.cn/problem/P1434

记忆化搜索。如果记录（x,y）到终点的代价，记忆化搜索是满足拓扑序的有向图，所以如果状态之间有双向的转移就会出错，本题题意（从高到地）决定了简单的记忆是可行的，否则就要另外处理了。

再比如，一个矩阵，如果规定只能向右向下是满足的，如果可以4个方向转移，就会出错。

最优性剪枝，记录起点到当前点（x,y）的代价。如果搜索到这点时，代价大于已记录的则剪去即可。

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
41
42
#include <bits/stdc++.h>
using namespace std;
#define sf(n) scanf("%d",&n)
#define pf(n) printf("%d",n)
#define fi(i,s,t) for(int i=s;i<t;i++)
#define mem(a,c) memset(a,c,sizeof(a))
const int MAX=100+5;
int n,m,a[MAX][MAX],ans,rec[MAX][MAX],vis[MAX][MAX];
int aw[4][2]={-1,0,0,1,1,0,0,-1};
bool judge(int x,int y){
	if(x<1 || x>n || y<1 ||y>m) return false;
	return true;
}
int dfs(int x,int y){
	if(rec[x][y]) return rec[x][y];
	int _max=0;
	fi(i,0,4){
		int tx= x + aw[i][0],ty= y + aw[i][1];
		if(judge(tx,ty) && !vis[tx][ty] && a[tx][ty] < a[x][y]) {
			vis[tx][ty] = 1;
			_max= max(_max,dfs(tx,ty)+1);
			vis[tx][ty] = 0;
		}
	}
	return rec[x][y]=_max;
}
int main(){
	freopen("in","r",stdin);
	sf(n);sf(m);
	ans=0;
	fi(i,1,n+1)
		fi(j,1,m+1)
			sf(a[i][j]);
	mem(rec,0);mem(vis,0);
	int _max=0;
	fi(i,1,n+1)
		fi(j,1,m+1){
			_max=max(_max,dfs(i,j));
		}
	pf(_max+1);
	return 0;
}